Name
Title | ||
|---|---|---|
Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings |
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\leq\sqrt{2n}$, the grid area is O(n5/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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-36763-2_34 | Graph Drawing |
DocType | Volume | Citations |
Journal | abs/1206.1919 | 3 |
PageRank | References | Authors |
0.58 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Castelli Aleardi | 1 | 87 | 7.96 |
| Olivier Devillers | 2 | 405 | 26.68 |
| Éric Fusy | 3 | 198 | 21.95 |