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

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.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2009, 42 (3), pp.489-516. 〈10.1007/s00454-009-9169-z〉
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00712046
Contributeur : Luca Castelli Aleardi <>
Soumis le : mardi 26 juin 2012 - 11:57:12
Dernière modification le : jeudi 10 mai 2018 - 02:06:33
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 02:40:08

Fichier

SchnyderWoods_DCG09_Hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

228

Téléchargements de fichiers

96