Lower Bounds on the Area Requirements of Series-Parallel Graphs
Fabrizio Frati
Abstract
We show that there exist series-parallel graphs requiring
Ω(n 2^√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
K2,n, one side of the bounding box has length
Ω(n), thus answering two questions posed by Biedl
et al. Second, we show a family of series-parallel graphs
requiring Ω(2^√log
n) width and Ω(2^√log n) height
in any straight-line or poly-line grid drawing. Combining the two
results, the Ω(n 2^√log
n) area lower bound is achieved.
Full Text: PDF PostScript