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 2) 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 2) area. Our drawings are visibility representations, which can be converted to polyline drawings of asymptotically the same area.