Straight-Line Triangle Representations via Schnyder Labelings
Vol. 19, no. 1, pp. 467-505, 2015. Regular paper.
Abstract A straight-line triangle representation (SLTR) of a planar graph is a straight-line drawing such that all the faces including the outer face are triangles. Such a drawing can be viewed as a tiling of a triangle with triangles where the input graph is the skeletal structure. A characterization based on flat angle assignments, i.e., selections of angles of the graph that are of size π in the representation, has been presented in earlier work. The drawback of this characterization of SLTRs is that we have no efficient algorithm for testing whether a given graph admits a flat angle assignment that fulfills the conditions. In this paper we present a new characterization based on Schnyder woods. For graphs with few Schnyder woods there exists a polynomial algorithm to check whether the conditions of this characterization are satisfied. However, there are planar 3-connected graphs on n vertices, which have 3.209n Schnyder woods. We also present a translation of the new characterization into a 2-commodity flow problem. Deciding whether a 2-commodity flow problem has an integral solution is known to be NP-complete. Hence, it is still open to decide whether the recognition of graphs that admit a straight line triangle representation is polynomially tractable.
Submitted: April 2015.
Reviewed: July 2015.
Revised: September 2015.
Accepted: September 2015.
Final: October 2015.
Published: October 2015.
Communicated by William S. Evans
article (PDF)