Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00453-011-9514-5 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
nash- williams theorem,4-regular map,additional property,regular plane graphs,schnyder wood,forest decomposition,distinguished vertex v,orthogonal drawing.,straight-line drawing,vertex v,additional row,algorithms place,d-regular plane graph,schnyder decomposition,. schnyder woods,additional bend,schnyder decompositions,schnyder labelling,4-regular plane graph | Journal | 62 |
Issue | ISSN | Citations |
3-4 | 1432-0541 | 5 |
PageRank | References | Authors |
0.51 | 23 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olivier Bernardi | 1 | 106 | 14.20 |
| Éric Fusy | 2 | 198 | 21.95 |