Schnyder woods for higher genus triangulated surfaces

Schnyder woods for higher genus triangulated surfaces
Luca Castelli Aleardi, Eric Fusy, Thomas Lewiner

Abstract:

We study a well-known characterization of planar graphs, also called Schnyder wood or Schnyder labeling, which yields a decomposition into vertex spanning trees. The goal is to extend previous algorithms and characterizations 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 the higher genus case. All the algorithms presented here have linear time complexity.

Downloads:

PDF paper (434 KB)

BibTeX:

@inproceedings{realizer_socg,
    author = {Luca Castelli Aleardi and Eric Fusy and Thomas Lewiner},
    title = {Schnyder woods for higher genus triangulated surfaces},
    year = {2008},
    month = {june},
    booktitle = {SoCG 2008 (XXIV ACM Symposium on Computational Geometry)},
    pages = {311--319},
    publisher = {ACM},
    doi = {10.1145/1377676.1377730},
    url = {\url{http://thomas.lewiner.org/pdfs/realizer_socg.pdf}}
}