Name
Title | ||
|---|---|---|
Canonical Ordering For Graphs On The Cylinder, With Applications To Periodic Straight-Line Drawings On The Flat Cylinder And Torus |
Abstract | ||
|---|---|---|
We extend the notion of canonical ordering, initially developed for planar triangulations and 3-connected planar maps, to cylindric triangulations and more generally to cylindric 3-connected maps. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix, Pach and Pollack and of Kant from the planar triangulated case and the 3-connected case to this setting. Precisely, for any cylindric essentially 3-connected map G with n vertices, we can obtain in linear time a straight-line drawing of G that is periodic in x-direction, crossing-free, and internally (weakly) convex. The vertices of this drawing lie on a regular grid Z/wZ x [0..4 with w <= 2n and h <= n(2d + 1), where d is the face-distance between the two boundaries. This also yields an efficient periodic drawing algorithm for graphs on the torus. Precisely, for any essentially 3-connected map G on the torus (i.e., 3-connected in the periodic representation) with n vertices, we can compute in linear time a periodic straight-line drawing of G that is crossing-free and (weakly) convex, on a periodic regular grid Z/wZ x Z/hZ, with w <= 2n and h <= 1 + 2n(c + 1), where c is the face-width of G. Since c < root 2n, the grid area is O(n(5/2)). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.20382/jocg.v9i1a14 | JOURNAL OF COMPUTATIONAL GEOMETRY |
DocType | Volume | Issue |
Journal | 9 | 1 |
ISSN | Citations | PageRank |
1920-180X | 0 | 0.34 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Castelli Aleardi | 1 | 87 | 7.96 |
| Olivier Devillers | 2 | 788 | 70.63 |
| Éric Fusy | 3 | 198 | 21.95 |