On the structure of Schnyder woods on orientable surfaces

DOI10.20382/JOCG.V10I1A5zbMATH Open1428.05077arXiv1501.05475OpenAlexW3014755076MaRDI QIDQ5224477FDOQ5224477

Authors: Kolja Knauer, Daniel Gonçalves, Benjamin Lévêque 

Publication date: 23 July 2019

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.

Full work available at URL: https://arxiv.org/abs/1501.05475

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

zbMATH Keywords

graph drawingorder dimensionSchnyder labeling

Mathematics Subject Classification ID

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)

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
• Embedding quadrangulations on a 2-book
• Schnyder woods and orthogonal surfaces
• 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)