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 , pp. 280-291(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_27).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_27
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1069

Actions (login required)

View Item View Item