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

Résumé : 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).
Type de document :
Rapport
[Research Report] RR-7989, INRIA. 2012
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00705181
Contributeur : Olivier Devillers <>
Soumis le : jeudi 7 juin 2012 - 09:36:41
Dernière modification le : jeudi 10 mai 2018 - 02:06:47
Document(s) archivé(s) le : lundi 10 septembre 2012 - 11:30:42

Fichier

RR-7989.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

421

Téléchargements de fichiers

307