Lower Bounds on the Area Requirements of Series-Parallel Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2010

Lower Bounds on the Area Requirements of Series-Parallel Graphs

Résumé

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.
Fichier principal
Vignette du fichier
1472-5804-2-PB.pdf (639.14 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00990461 , version 1 (13-05-2014)

Identifiants

Citer

Fabrizio Frati. Lower Bounds on the Area Requirements of Series-Parallel Graphs. Discrete Mathematics and Theoretical Computer Science, 2010, Vol. 12 no. 5 (5), pp.139-174. ⟨10.46298/dmtcs.500⟩. ⟨hal-00990461⟩

Collections

TDS-MACS
61 Consultations
729 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More