Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs
Small Drawings of Series-Parallel Graphs and Other Subclasses of Planar Graphs
复制标题
串并联图和平面图其他子类的小图
DOI：
10.1007/978-3-642-11805-0_27
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
T. Biedl
中科院分区：
文献类型：
--
作者：
T. Biedl
本文研究平面图的小平面图。对于任意平面图，Θ（n2）是最坏情况面积的上界和下界。什么样的图可以获得更小的面积是一个长期存在的问题，目前只知道树和外平面图的结果。本文证明了串-并联图可以在O（n ~ 3/2）的面积内画出，而2-外平面图和适当路宽为3的平面图则需要Ω（n ~ 2）的面积。
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 inO(n3/2) area, but 2-outer-planar graphs and planar graphs of proper pathwidth 3 require Ω(n2) area.