Algorithms for Plane Representations of Acyclic Digraphs
Algorithms for Plane Representations of Acyclic Digraphs
复制标题
DOI：
10.1016/0304-3975(88)90123-5
复制
发表时间：
1988-11
期刊：
影响因子：
--
通讯作者：
G. Battista;R. Tamassia
中科院分区：
文献类型：
--
作者：
G. Battista;R. Tamassia
无圈有向图广泛用于表示层次结构。例子包括PERT网络，子程序调用图，家谱，组织结构图，Hasse图和伊萨层次结构中的知识表示图。我们研究的问题，表示无圈有向图在这样一种方式，所有的边缘流在同一个方向，例如，从左到右或从下到上。三个平面表示被认为是：直的图纸，可见性表示，和网格图纸。我们提供了有效的算法，构建这些表示与所有的边缘在同一方向流动。对于可见性表示和网格图，时间复杂度为O（n），对于直线图，时间复杂度为O（nlogn），其中n是有向图的顶点数。对于格的覆盖有向图，构造直图的复杂度为O（n）。我们还证明了，平面有向图，承认这些表示的任何一个正是子图的平面图。
Acyclic digraphs are widely used for representing hierarchical structures. Examples include PERT networks, subroutine-call graphs, family trees, organization charts, Hasse diagrams, and ISA hierarchies in knowledge representation diagrams. We investigate the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top. Three plane representations are considered:straight drawings,visibility representations, andgrid drawings. We provide efficient algorithms that construct these representations with all edges flowing in the same direction. The time complexity is O(n) for visibility representations and grid drawings, and O(nlogn) for straight drawings, wherenis the number of vertices of the digraph. For covering digraphs of lattices, the complexity of constructing straight drawings is O(n). We also show that the planar digraphs that admit any one of these representations are exactly the subgraphs of planarst-graphs.