Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990461
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 3:37:41 PM
Last modification on : Thursday, June 18, 2020 - 12:46:02 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:18:37 PM

File

1472-5804-2-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

55

Files downloads

535