Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2013-005 (August 9, 2013)
Straight-line Drawability of Embedded Graphs
by Hiroshi Nagamochi
The fact that every plane embedding $\gamma$ of a simple graph $G$
admits a straight-line plane drawing $D$ is known as Fary's theorem.
The result has been extended to the class of 1-planar graphs by
Thomassen by identifying two kinds of forbidden configurations, a
topological characterization of all 1-plane embeddings $\gamma$ that do
not admit straight-line 1-plane drawings.
In this paper, we first consider the classical problem setting which
asks whether a given embedding $\gamma$ admits a straight-line drawing
$D$ with the same planarization of $\gamma$, and show that there is a 3
-plane and quasi-plane embedding that admits no straight-line drawing
and cannot be characterized by a natural extension of forbidden
We next formulate a slightly relaxed problem setting which asks whether
a given embedding $\gamma$ of a graph $G$ admits a straight-line drawing
$D$ under the same ``frame," which is defined by a fixed biconnected
plane spanning subgraph of $G$.
We prove that a given embedding admits a straight-line drawing under
the same frame if and only if it contains none of our forbidden
configurations. One of our consequences is that if a given embedding is
quasi-plane and its crossing-free edges induce a biconnected spanning
subgraph, then its straight-line drawability (in the classical sense)
can be checked by our forbidden configurations in polynomial time.
Our result also implies several previously known results on straight-
line drawings such as the convex-drawability of biconnected plane