Skip to Main content Skip to Navigation
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

https://hal.inria.fr/hal-00712062
Contributor : Luca Castelli Aleardi <>
Submitted on : Tuesday, June 26, 2012 - 12:16:42 PM
Last modification on : Friday, December 18, 2020 - 5:12:01 PM
Long-term archiving on: : Thursday, September 27, 2012 - 2:40:15 AM

File

SchnyderWoodsHigherGenus_SoCG_...
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

451

Files downloads

313