Drawing Planar Partitions II: HH-Drawings
Drawing Planar Partitions II: HH-Drawings
复制标题
绘制平面分区 II：HH 绘图
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Petra Mutzel
中科院分区：
文献类型：
--
作者：
T. Biedl;M. Kaufmann;Petra Mutzel
设平面图G=（V，E），点划分V=A B.我们能画出没有边交叉的G，使得划分清晰可见吗？这些图形有助于显示在各种应用程序中出现的分区和切口。本文研究了图G中顶点类A和B由一条水平线分开的平面图（即所谓的HH-图）。本文给出了所谓的y-单调平面HH-图存在的充要条件，并给出了一个线性时间算法来构造（如果可能的话）具有少量弯曲的面积（{cal O}（vert Vvert ^2））的y-单调平面HH-图.此外，我们给出了直线平面HH-图面积的指数下界。最后，我们研究了非y-单调的平面HH-图。
Let a planar graph G=(V,E) and a vertex-partition V=A ∪ B be given. Can we draw G without edge crossings such that the partition is clearly visible? Such drawings aid to display partitions and cuts as they arise in various applications. In this paper, we study planar drawings of G in which the vertex classes A and B are separated by a horizontal line (so-called HH-drawings). We provide necessary and sufficient conditions for the existence of so-called y-monotone planar HH-drawings, and a linear time algorithm to construct, if possible, a y-monotone planar HH-drawing of area ({cal O}(vert Vvert^2)) with few bends. Furthermore, we give an exponential lower bound for the area of straight-line planar HH-drawings. Finally, we study planar HH-drawings that are not y-monotone.