Small Drawings of Outerplanar Graphs,Series-Parallel Graphs,and Other Planar Graphs

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n ²) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be achieved. We show here that series-parallel graphs can be drawn in O(n ^3/2) area, and outerplanar graphs can be drawn in O(nlog n) area, but 2-outerplanar graphs and planar graphs of proper pathwidth 3 require Ω(n ²) area. Our drawings are visibility representations, which can be converted to polyline drawings of asymptotically the same area.