Straight-Line Triangle Representations via Schnyder Labelings

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 at 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 ecient algorithm for testing whether a given graph admits a at angle assignment that fullls 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 satised. However, there are planar 3-connected graphs on