Discrete Mathematics & Theoretical Computer Science, Vol 12, No 5 (2010)

Font Size:  Small  Medium  Large

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