Skip to Main content Skip to Navigation
New interface
Conference papers

Schnyder woods for higher genus triangulated surfaces

Abstract : Schnyder woods are a well known combinatorial structure for planar graphs, which yields a decomposition into 3 vertex-spanning trees. Our goal is to extend definitions and algorithms for Schnyder woods designed for planar graphs (corresponding to combinatorial surfaces with the topology of the sphere, i.e., of genus 0) to the more general case of graphs embedded on surfaces of arbitrary genus. First, we define a new traversal order of the vertices of a triangulated surface of genus g together with an orientation and coloration of the edges that extends the one proposed by Schnyder for the planar case. As a by-product we show how some recent schemes for compression and compact encoding of graphs can be extended to higher genus. All the algorithms presented here have linear time complexity.
Document type :
Conference papers
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Luca Castelli Aleardi Connect in order to contact the contributor
Submitted on : Tuesday, June 26, 2012 - 12:16:42 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:33 PM
Long-term archiving on: : Thursday, September 27, 2012 - 2:40:15 AM


Files produced by the author(s)




Luca Castelli Aleardi, Eric Fusy, Thomas Lewiner. Schnyder woods for higher genus triangulated surfaces. 24th ACM annual symposium on Computational geometry, Jun 2008, University of Maryland, College Park, United States. pp.311-319, ⟨10.1145/1377676.1377730⟩. ⟨hal-00712062⟩



Record views


Files downloads