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 tri-angulations 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 × [0..h], 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 × Z/hZ, with w ≤ 2n and h ≤ 1 + 2n(c + 1), where c is the face-width of G. Since c ≤ √ 2n, the grid area is O(n 5/2).
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download


https://hal.inria.fr/hal-01959590
Contributor : Olivier Devillers <>
Submitted on : Tuesday, December 18, 2018 - 6:27:03 PM
Last modification on : Thursday, November 7, 2019 - 3:58:02 PM
Long-term archiving on : Wednesday, March 20, 2019 - 12:16:40 PM

Files

360-1657-1-PB.pdf
Files produced by the author(s)

Identifiers

Citation

Luca Castelli Aleardi, Olivier Devillers, Eric Fusy. Canonical Ordering for Graphs on the Cylinder with Applications to Periodic Straight-line Drawings on the Flat Cylinder and Torus. Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2018, 9 (1), pp.391 - 429. ⟨10.20382/jocg.v9i1a14⟩. ⟨hal-01959590⟩

Share

Metrics

Record views

95

Files downloads

45