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

Luca Castelli Aleardi (1) , Eric Fusy (1) , Thomas Lewiner (2)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 PUC-Rio - Pontifícia Universidade Católica do Rio de Janeiro [Brasil] = Pontifical Catholic University of Rio de Janeiro [Brazil] = Université catholique pontificale de Rio de Janeiro [Brésil]

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.

Mots clés: Schnyder woods; graph encoding; triangulations; higher genus maps

Domaines: Géométrie algorithmique [cs.CG]

Luca Castelli Aleardi, Eric Fusy, Thomas Lewiner. Schnyder woods for higher genus triangulated surfaces, with applications to encoding. Discrete and Computational Geometry, 2009, 42 (3), pp.489-516. ⟨10.1007/s00454-009-9169-z⟩. ⟨hal-00712046⟩