Loading...
research article
Lower Bounds on the Area Requirements of Series-Parallel Graphs
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,K-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
research article
Web of Science ID
WOS:000292683500004
Authors
Publication date
2010
Volume
12
Issue
5
Start page
139
End page
174
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 26, 2010
Use this identifier to reference this record