论文标题
频率边缘很少的ST定向
st-Orientations with Few Transitive Edges
论文作者
论文摘要
定向无方向图的边缘的问题，使得最终的图形是无环的，并且具有单个源S，并且单个接收器T在图理论中具有较长的传统，并且对于许多图形绘图算法是核心。这种方向称为ST取向。我们解决了计算不向图的分类方向的问题，该图形数量最小的及物边缘数量。在一般情况下，我们证明了问题是NP-HARD。对于平面图，我们描述了一个在实践中快速的ILP模型。我们从实验上表明，相对于通过经典的ST-numbering算法计算出的不受约束的ST定向，最佳解决方案大大减少了及传递边缘的数量。此外，专注于将ST取向作为初步步骤的流行图形绘图算法，我们表明减少及时边缘的数量会导致图纸更紧凑。
The problem of orienting the edges of an undirected graph such that the resulting digraph is acyclic and has a single source s and a single sink t has a long tradition in graph theory and is central to many graph drawing algorithms. Such an orientation is called an st-orientation. We address the problem of computing st-orientations of undirected graphs with the minimum number of transitive edges. We prove that the problem is NP-hard in the general case. For planar graphs we describe an ILP model that is fast in practice. We experimentally show that optimum solutions dramatically reduce the number of transitive edges with respect to unconstrained st-orientations computed via classical st-numbering algorithms. Moreover, focusing on popular graph drawing algorithms that apply an st-orientation as a preliminary step, we show that reducing the number of transitive edges leads to drawings that are much more compact.
