Skip to Main content Skip to Navigation
Conference papers

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.
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 : Thursday, March 5, 2020 - 6:28:52 PM
Document(s) archivé(s) le : 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

772

Files downloads

350