Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-line Drawings - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

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

(1) , (2) , (1)
1
2

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.
Fichier principal
Vignette du fichier
GD_Hal.pdf (441.26 Ko) Télécharger le fichier
Vignette du fichier
vignette-hal-00793636.jpg (66.66 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

hal-00793636 , version 1 (22-02-2013)

Identifiers

Cite

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. pp.376-387, ⟨10.1007/978-3-642-36763-2_34⟩. ⟨hal-00793636⟩
373 View
145 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More