Schnyder woods for higher genus triangulated surfaces, with applications to encoding

Schnyder woods for higher genus triangulated surfaces, with applications to encoding
Luca Castelli Aleardi, Eric Fusy, Thomas Lewiner

Abstract:

Schnyder woods are a well-known combinatorial structure for plane triangulations, which yields a decomposition into 3 spanning trees. We extend here definitions and algorithms for Schnyder woods to closed orientable surfaces of arbitrary genus. In particular, we describe a method to traverse a triangulation of genus g and compute a so-called g-Schnyder wood on the way. As an application, we give a procedure to encode a triangulation of genus g and n vertices in 4n+O(g log(n)) bits. This matches the worst-case encoding rate of Edgebreaker in positive genus. All the algorithms presented here have execution time O((n+g)g), hence are linear when the genus is fixed.

Downloads:

PDF paper (589 KB)

BibTeX:

@article{realizer_dcg,
    author = {Luca Castelli Aleardi and Eric Fusy and Thomas Lewiner},
    title = {Schnyder woods for higher genus triangulated surfaces, with applications to encoding},
    year = {2009},
    month = {october},
    journal = {Discrete and Computational Geometry},
    volume = {42},
    number = {3},
    pages = {489--516},
    publisher = {Springer},
    doi = {10.1007/s00454-009-9169-z},
    url = {\url{http://thomas.lewiner.org/pdfs/realizer_dcg.pdf}}
}