## Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings
Castelli Aleardi, Luca and Devillers, Olivier and Fusy, Éric
(2013)
Full text not available from this repository. ## AbstractWe 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 $ℤ/wℤ×[0..h]$, with $w ≤ 2n$ and $h ≤ 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$ ℤ/wℤ×ℤ/hℤ$, with $w ≤ 2n$ and $h ≤ 1 + n(2c + 1)$, where c is the length of a shortest non-contractible cycle. Since $c≤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.
Repository Staff Only: item control page References |