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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download


https://hal.inria.fr/hal-00793636
Contributor : Luca Castelli Aleardi <>
Submitted on : Friday, February 22, 2013 - 4:34:37 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 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

747

Files downloads

289