Schnyder Decompositions for Regular Plane Graphs and Application to Drawing

Schnyder woods are decompositions of simple triangulations into three edge‐disjoint spanning trees crossing each other in a specific way. In this article, we generalize the definition of Schnyder woods to d‐angulations (plane graphs with faces of degree d) for all d≥3. A Schnyder decomposition is a set of d spanning forests crossing each other in a specific way, and such that each internal edge is part of exactly d-2 of the spanning forests. We show that a Schnyder decomposition exists if and only if the girth of the d‐angulation is d. As in the case of Schnyder woods (d=3), there are alternative formulations in terms of orientations (‘fractional’ orientations when d≥5) and in terms of corner‐labellings. Moreover, the set of Schnyder decompositions of a fixed d‐angulation of girth d has a natural structure of distributive lattice. We also study the dual of Schnyder decompositions which are defined on d‐regular plane graphs of mincut d with a distinguished vertex v ^*: these are sets of d spanning trees rooted at v ^* crossing each other in a specific way and such that each edge not incident to v ^* is used by two trees in opposite directions. Additionally, for even values of d, we show that a subclass of Schnyder decompositions, which are called even, enjoy additional properties that yield a reduced formulation; in the case d=4, these correspond to well‐studied structures on simple quadrangulations (2‐orientations and partitions into 2 spanning trees). In the case d=4, we obtain straight‐line and orthogonal planar drawing algorithms by using the dual of even Schnyder decompositions. For a 4‐regular plane graph G of mincut 4 with a distinguished vertex v ^* and n-1 other vertices, our algorithms places the vertices of G\v ^* on a (n-2)×(n-2) grid according to a permutation pattern, and in the orthogonal drawing each of the 2n-4 edges of G\v ^* has exactly one bend. The vertex v ^* can be embedded at the cost of 3 additional rows and columns, and 8 additional bends. We also describe a further compaction step for the drawing algorithms and show that the obtained grid‐size is strongly concentrated around 25n/32×25n/32 for a uniformly random instance with n vertices.