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

Castelli Aleardi, Luca and Devillers, Olivier and Fusy, Éric (2013) Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 376-387(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.

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 \$ℤ/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.

Item Type: Conference Paper 10.1007/978-3-642-36763-2_34 G Algorithms and Complexity > G.280 Canonical OrderingP Styles > P.720 Straight-line UNSPECIFIED Administration GDEA 21 Nov 2013 16:12 21 Nov 2013 16:12 http://gdea.informatik.uni-koeln.de/id/eprint/1326