On upward drawing testing of triconnected digraphs (extended abstract)
On upward drawing testing of triconnected digraphs (extended abstract)
复制标题
DOI：
10.1145/109648.109679
复制
发表时间：
1991-06
期刊：
影响因子：
--
通讯作者：
P. Bertolazzi;G. Battista
中科院分区：
文献类型：
--
作者：
P. Bertolazzi;G. Battista
在本文中，我们解决了，对于三连通有向图，存在的P-时间算法的问题，以测试是否有一个向上的绘图，即绘图，使所有的边缘指向向上。这个问题出现在有序集和自动绘图领域，并从几年前开始开放。该算法的时间复杂度为O（n + r3/ogr），其中n为顶点数，r为有向图的源和汇数.
In this paper we solve, for triconnected digraphs, the problem of the existence of a P-time algorithm for testing if a digraph has an upward drawing, i.e. a drawing such that all the edges point upward. The problem arises in the fields of ordered sets and automatic graph drawing and was open from several years. The time complexity of the proposed algorithm is O(n + r3/ogr), where n is the number of vertices and r is the number of sources and sinks of the digraph.