Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2012

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

(1) , (2) , (1)
1
2

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).
Nous étendons la notion d'ordre canonique à des triangulations cylindriques. L'algorithme incrémental de tracé de graphe planaire introduit par de Fraysseix et al. peut ainsi être étendu au cas cylindrique. Notre algorithme permet d'obtenir en temps linéaire un tracé linéaire sans croisement d'une triangulation cylindrique T avec n sommets sur la grille régulière Z/wZ×[0,h], où w ≤ 2n et h ≤ n(2d+1), avec d la distance (en nombre d'arètes de la triangulation) entre les deux bords. On peut en déduire un algorithme en temps linéaire pour un tracé linéaire sans croisement d'une triangulation du tore sur la grille périodique Z/wZ×Z/hZ, où w ≤ 2n et h ≤ 1+n(2c+1), avec c la longueur du plus court cycle non contractible. Comme c ≤ √2n}, l'aire de la grille est en O(n²√n).
Fichier principal
Vignette du fichier
RR-7989.pdf (690.3 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00705181 , version 1 (07-06-2012)

Identifiers

  • HAL Id : hal-00705181 , version 1

Cite

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⟩
202 View
167 Download

Share

Gmail Facebook Twitter LinkedIn More