Aller au menu Aller au contenu
Consultez les publications et les thèses
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Consultez les publications et les thèses
Consultez les publications et les thèses

> GSCOP_PRODUCTION > Thèses soutenues


Auteur : Benjamin LEVÊQUE
Date : 19 ocotbre 2016

Generalization of Schnyder woods to orientable surfaces and applications
Schnyder woods are particularly elegant combinatorial structures with numerous applications concerning planar triangulations and more generally 3-connected planar maps. We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of any genus with a special emphasis on the toroidal case. We provide a natural partition of the set of Schnyder woods of a given map into distributive lattices depending on the surface homology. In the toroidal case we show the existence of particular Schnyder woods with some global properties that are useful for optimal encoding or graph drawing purpose.

Mots-clés : Embedded graphs, Orientables surfaces, Toroidal triangulations, 3-connected maps, alpha-orientations, Schnyder woods, Distributive lattices, Homology, Bijective encoding, Graph drawing

mise à jour le 15 septembre 2016

Université Grenoble Alpes