Skip to Main content Skip to Navigation
Journal articles

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

Daniel Gonçalves 1 Benjamin Lévêque 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01263819
Contributor : Daniel Goncalves <>
Submitted on : Wednesday, January 29, 2020 - 4:50:42 PM
Last modification on : Thursday, July 16, 2020 - 3:32:46 PM
Document(s) archivé(s) le : Thursday, April 30, 2020 - 6:42:23 PM

File

1202.0911.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

243

Files downloads

125