Toroidal Maps: Schnyder Woods, Orthogonal Surfaces and Straight-Line Representations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete and Computational Geometry Année : 2014

Toroidal Maps: Schnyder Woods, Orthogonal Surfaces and Straight-Line Representations

Benjamin Lévêque

Résumé

A Schnyder wood is an orientation and coloring of the edges of a planar map satisfying a simple local property. We propose a generalization of Schnyder woods to graphs embedded on the torus with application to graph drawing. We prove several properties on this new object. Among all we prove that a graph embedded on the torus admits such a Schnyder wood if and only if it is an essentially 3-connected toroidal map. We show that these Schnyder woods can be used to embed the universal cover of an essentially 3-connected toroidal map on an infinite and periodic orthogonal surface. Finally we use this embedding to obtain a straight-line flat torus representation of any toroidal map in a polynomial size grid.
Fichier principal
Vignette du fichier
1202.0911.pdf (645.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01263819 , version 1 (29-01-2020)

Identifiants

Citer

Daniel Gonçalves, Benjamin Lévêque. Toroidal Maps: Schnyder Woods, Orthogonal Surfaces and Straight-Line Representations. Discrete and Computational Geometry, 2014, 51 (1), pp.67-131. ⟨10.1007/s00454-013-9552-7⟩. ⟨lirmm-01263819⟩
128 Consultations
95 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More