### 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 K_{2,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