Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs
Biedl, Therese (2010) Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 280-291 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_27).
Full text not available from this repository.
In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n2 ) 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(n3/2 ) area, but 2-outer-planar graphs and planar graphs of proper pathwidth 3 require Ω(n2 ) area.
Repository Staff Only: item control page