Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-line Drawings

Abstract : We extend the notion of canonical orderings to cylindric triangulations. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix, Pach and Pollack to this setting. Our algorithm yields in linear time a crossing-free straight-line drawing of a cylindric triangulation $G$ with $n$ vertices on a regular grid $\mZ/w\mZ\times[0..h]$, with $w\leq 2n$ and $h\leq n(2d+1)$, where $d$ is the (graph-) distance between the two boundaries. As a by-product, we can also obtain in linear time a crossing-free straight-line drawing of a toroidal triangulation with $n$ vertices on a periodic regular grid $\mZ/w\mZ\times\mZ/h\mZ$, with $w\leq 2n$ and $h\leq 1+n(2c+1)$, where $c$ is the length of a shortest non-contractible cycle. Since $c\leq\sqrt{2n}$, the grid area is $O(n^{5/2})$. Our algorithms apply to any triangulation (whether on the cylinder or on the torus) that have no loops nor multiple edges in the periodic representation.
Type de document :
Communication dans un congrès
Graph Drawing - 20th International Symposium, GD 2012, Sep 2012, Redmond, WA, United States. Springer, 7704, pp.376-387, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-36763-2_34〉
Liste complète des métadonnées

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


https://hal.inria.fr/hal-00793636
Contributeur : Luca Castelli Aleardi <>
Soumis le : vendredi 22 février 2013 - 16:34:37
Dernière modification le : jeudi 12 avril 2018 - 01:49:03
Document(s) archivé(s) le : dimanche 2 avril 2017 - 04:25:36

Fichiers

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

Identifiants

Collections

Citation

Luca Castelli Aleardi, Olivier Devillers, Eric Fusy. Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-line Drawings. Graph Drawing - 20th International Symposium, GD 2012, Sep 2012, Redmond, WA, United States. Springer, 7704, pp.376-387, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-36763-2_34〉. 〈hal-00793636〉

Partager

Métriques

Consultations de la notice

513

Téléchargements de fichiers

175