Straight-Line Triangle Representations via Schnyder Labelings

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.209ⁿ 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.