On the structure of Schnyder woods on orientable surfaces
From MaRDI portal
Publication:5224477
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) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
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
(17)- Lattice structures from planar graphs
- Blossoming bijection for higher-genus maps
- Schnyder decompositions for regular plane graphs and application to drawing
- Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations
- Flips on homologous orientations of surface graphs with prescribed forbidden facial cycles
- Orienting triangulations
- Schnyder Woods and Orthogonal Surfaces
- Embedding quadrangulations on a 2-book
- Encoding toroidal triangulations
- Schnyder woods for higher genus triangulated surfaces (abstract)
- Binary labelings for plane quadrangulations and their relatives
- Structural parameters of Schnyder woods
- A bijection for essentially 4-connected toroidal triangulations
- Lattice structure for orientations of graphs
- Computation of toroidal Schnyder woods made simple and fast: from theory to practice
- Schnyder woods for higher genus triangulated surfaces, with applications to encoding
- Schnyder woods and orthogonal surfaces
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)
