Area requirement and symmetry display of planar upward drawings
Area requirement and symmetry display of planar upward drawings
复制标题
平面向上图的面积要求和对称性显示
DOI：
--
复制
发表时间：
1992
影响因子：
0.8
通讯作者：
I. Tollis
中科院分区：
文献类型：
--
作者：
G. Battista;R. Tamassia;I. Tollis
在本文中，我们研究了构造非循环有向图的平面直线图的问题，使得所有边都沿相同方向流动，例如从下到上。我们的贡献是双重的。首先，我们展示一系列平面无环有向图的存在，任何此类绘图都需要指数面积。其次，受前面下限的启发，我们放宽直线约束并允许沿边缘弯曲。我们提出了一种线性时间算法，可以生成具有少量弯曲、渐近最优区域的平面图的绘图，从而显示有向图的对称性和同构性。如果有向图没有传递边，则获得的图形没有弯曲。此外，该算法的一种变体可以生成具有精确最小面积的绘图。
In this paper we investigate the problem of constructing planar straight-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g., from bottom to top. Our contribution is twofold. First we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings of planarst-graphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges, then the drawing obtained has no bends. Also, a variation of the algorithm produces drawings with exact minimum area.