Henneberg steps for triangle representations
Nieke Aerts, Stefan Felsner · Scuola Normale Superiore eBooks · 2013
Which plane graphs admit a straight line representation such that all faces have the shape of a triangle? In previous work we have studied necessary and sufficient conditions based on flat angle assignments, i.e., selections of angles of the graph that have size π in the representation. A flat angle assignment that fullfills these conditions is called good. The complexity for checking whether a graph has a good flat angle assignment remains unknown. In this paper we deal with extensions of good flat angle assignments. We show that if G has a good flat angle assignment and G + is obtained via a planar Henneberg step of type 2, then G + also admits a good flat angle assignment. A similar result holds for certain combinations of Henneberg type 1 steps followed by a type 2 step. As a consequence we obtain a large class of pseudo-triangulations that admit drawings such that all faces have the shape of a triangle. In particular, every 3-connected, plane generic circuit admits a good flat angle assignment. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.