On the structure of Schnyder woods on orientable surfaces
From MaRDI portal
Publication:5224477
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Relations of low-dimensional topology with graph theory (57M15)
Abstract: We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of higher genus. This is done in the language of angle labelings. Generalizing results of De Fraysseix and Ossona de Mendez, and Felsner, we establish a correspondence between these labelings and orientations and characterize the set of orientations of a map that correspond to such a Schnyder labeling. Furthermore, we study the set of these orientations of a given map and provide a natural partition into distributive lattices depending on the surface homology. This generalizes earlier results of Felsner and Ossona de Mendez. In the toroidal case, a new proof for the existence of Schnyder woods is derived from this approach.
Recommendations
- Schnyder woods for higher genus triangulated surfaces (abstract)
- Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations
- Lattice structures from planar graphs
- Schnyder woods for higher genus triangulated surfaces, with applications to encoding
- Schnyder Woods and Orthogonal Surfaces
Cited in
(15)- Blossoming bijection for higher-genus maps
- Schnyder woods for higher genus triangulated surfaces, with applications to encoding
- Lattice structures from planar graphs
- Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations
- Schnyder woods and orthogonal surfaces
- Embedding quadrangulations on a 2-book
- Binary labelings for plane quadrangulations and their relatives
- Orienting triangulations
- Schnyder decompositions for regular plane graphs and application to drawing
- Schnyder Woods and Orthogonal Surfaces
- Structural parameters of Schnyder woods
- A bijection for essentially 4-connected toroidal triangulations
- Flips on homologous orientations of surface graphs with prescribed forbidden facial cycles
- Schnyder woods for higher genus triangulated surfaces (abstract)
- Encoding toroidal triangulations
This page was built for publication: On the structure of Schnyder woods on orientable surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224477)
