Skip to Main content Skip to Navigation
Journal articles

On the structure of Schnyder woods on orientable surfaces

Daniel Gonçalves 1 Kolja Knauer 2 Benjamin Lévêque 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 G-SCOP_OC [?-2015] - Optimisation Combinatoire [?-2015]
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
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 particular case of toroidal triangulations, this study enables us to identify a canonical lattice that lies at the core of several bijection proofs.
Document type :
Journal articles
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02407874
Contributor : Daniel Gonçalves <>
Submitted on : Thursday, December 12, 2019 - 4:41:26 PM
Last modification on : Friday, July 10, 2020 - 1:26:02 PM
Document(s) archivé(s) le : Friday, March 13, 2020 - 11:22:02 PM

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Daniel Gonçalves, Kolja Knauer, Benjamin Lévêque. On the structure of Schnyder woods on orientable surfaces. Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2019, 10 (1), pp.127-164. ⟨10.20382/jocg.v10i1a5⟩. ⟨lirmm-02407874⟩

Share

Metrics

Record views

39

Files downloads

29