Lower Bounds on the Area Requirements of Series-Parallel Graphs

Abstract : We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K(2,n), one side of the bounding box has length Omega(n), thus answering two questions posed by Biedl et al. Second, we show a family of series-parallel graphs requiring Omega(2(root log n)) width and Omega(2(root log n)) height in any straight-line or poly-line grid drawing. Combining the two results, the Omega(n2(root log n)) area lower bound is achieved.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (5), pp.139-174
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990461
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:41
Dernière modification le : mardi 3 octobre 2017 - 01:15:39
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:18:37

Fichier

1472-5804-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990461, version 1

Collections

Citation

Fabrizio Frati. Lower Bounds on the Area Requirements of Series-Parallel Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (5), pp.139-174. 〈hal-00990461〉

Partager

Métriques

Consultations de la notice

65

Téléchargements de fichiers

227