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).
Skip to Main content Skip to Navigation
Conference papers

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

Luca Castelli Aleardi 1 Olivier Devillers 2 Eric Fusy 1 
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download


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)

Identifiers

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

Share

Metrics

Record views

371

Files downloads

137