Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-00705181 , version 1

Citer

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⟩
201 Consultations
178 Téléchargements

Partager

Gmail Facebook X LinkedIn More