Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic StraightLine DrawingsCastelli Aleardi, Luca and Devillers, Olivier and Fusy, Éric (2013) Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic StraightLine Drawings. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 376387(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractWe extend the notion of canonical orderings to cylindric triangulations. This allows us to extend the incremental straightline drawing algorithm of de Fraysseix, Pach and Pollack to this setting. Our algorithm yields in linear time a crossingfree straightline 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 byproduct, we can also obtain in linear time a crossingfree straightline 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 noncontractible 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.
Actions (login required)
