Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings

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.