TY - GEN
T1 - Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings
AU - Castelli Aleardi, Luca
AU - Devillers, Olivier
AU - Fusy, Éric
PY - 2013/2/26
Y1 - 2013/2/26
N2 - 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 ≤ √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.
AB - 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 ≤ √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.
U2 - 10.1007/978-3-642-36763-2_34
DO - 10.1007/978-3-642-36763-2_34
M3 - Conference contribution
AN - SCOPUS:84874135087
SN - 9783642367625
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 376
EP - 387
BT - Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers
T2 - 20th International Symposium on Graph Drawing, GD 2012
Y2 - 19 September 2012 through 21 September 2012
ER -