Small Drawings of Series-Parallel Graphs and Other Subclasses of 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.It is a long-standing open problem for what graphs smaller area can be achieved, with results known only for trees and outer-planar graphs.We show here that series-parallel can be drawn in O(n~(3/2)) area, but 2-outer-planar graphs and planar graphs of proper pathwidth 3 require Ω(n~2) area.