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.
Type de document :
Communication dans un congrès
24th ACM annual symposium on Computational geometry, Jun 2008, University of Maryland, College Park, United States. ACM, pp.311-319, 2008, 〈10.1145/1377676.1377730〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00712062
Contributeur : Luca Castelli Aleardi <>
Soumis le : mardi 26 juin 2012 - 12:16:42
Dernière modification le : jeudi 12 avril 2018 - 01:46:24
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 02:40:15

Fichier

SchnyderWoodsHigherGenus_SoCG_...
Fichiers produits par l'(les) auteur(s)

Identifiants

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. ACM, pp.311-319, 2008, 〈10.1145/1377676.1377730〉. 〈hal-00712062〉

Partager

Métriques

Consultations de la notice

156

Téléchargements de fichiers

47