Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00372
StraightLine Triangle Representations via Schnyder Labelings
Vol. 19, no. 1, pp. 467505, 2015. Regular paper.
Abstract A straightline triangle representation (SLTR) of a planar graph is a straightline 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 3connected graphs on n vertices, which have 3.209^{n} Schnyder woods. We also present a translation of the new characterization into a 2commodity flow problem. Deciding whether a 2commodity flow problem has an integral solution is known to be NPcomplete. 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

Journal Supporters
