Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).

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

2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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.
Keywords :
Document type :
Conference papers

Cited literature [15 references]

https://hal.inria.fr/hal-00793636
Contributor : Luca Castelli Aleardi Connect in order to contact the contributor
Submitted on : Friday, February 22, 2013 - 4:34:37 PM
Last modification on : Thursday, January 20, 2022 - 5:27:28 PM
Long-term archiving on: : Sunday, April 2, 2017 - 4:25:36 AM

### Files

GD_Hal.pdf
Files produced by the author(s)

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

Record views