Small Area Drawings of Outerplanar Graphs
Small Area Drawings of Outerplanar Graphs
复制标题
外平面图的小面积图
作者：
G. Battista;Fabrizio Frati
摘要
我们给出了三个构造外平面图的平面直线网格图的线性时间算法。第一个和第二个算法是针对平衡外平面图的。两者都需要线性区域。第一种算法产生的图形不是外平面的，而第二种算法产生的图形是外平面的。另一方面，第一算法构造具有更好的角分辨率的绘图。第三个算法构造了面积为O（n1.48）的一般外平面图的外平面图。进一步，我们研究了外平面图的面积要求与其对偶树的一类特殊图的面积要求之间的相互影响。
Abstract
We show three linear-time algorithms for constructing planar straight-line grid drawings of outerplanar graphs. The first and the second algorithm are for balanced outerplanar graphs. Both require linear area. The drawings produced by the first algorithm are not outerplanar while those produced by the second algorithm are. On the other hand, the first algorithm constructs drawings with better angular resolution. The third algorithm constructs outerplanar drawings of general outerplanar graphs with O(n1.48) area. Further, we study the interplay between the area requirements of the drawings of an outerplanar graph and the area requirements of a special class of drawings of its dual tree.