Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2013-005 (August 9, 2013)

Straight-line Drawability of Embedded Graphs
by Hiroshi Nagamochi

pdf File


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 configurations either. 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 graphs.