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 et al. to this setting. Our algorithm yields in linear time a crossing-free straight-line drawing of a cylindric triangulation T with n vertices on a regular grid Z/wZ×[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 Z/wZ×Z/hZ, 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²√n).
Document type :
Reports
Liste complète des métadonnées

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00705181
Contributor : Olivier Devillers <>
Submitted on : Thursday, June 7, 2012 - 9:36:41 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Document(s) archivé(s) le : Monday, September 10, 2012 - 11:30:42 AM

File

RR-7989.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00705181, version 1

Collections

Citation

Luca Castelli Aleardi, Olivier Devillers, Eric Fusy. Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings. [Research Report] RR-7989, INRIA. 2012. ⟨hal-00705181⟩

Share

Metrics

Record views

445

Files downloads

335