论文标题
比较两个分层绘图框架的算法和实验
Algorithms and Experiments Comparing Two Hierarchical Drawing Frameworks
论文作者
论文摘要
我们提出算法，该算法扩展了基于路径的分层绘图框架并给出实验结果。我们的算法以$ o（km）$时间运行，其中$ k $是路径的数量，$ m $是图的边缘数，并且提供的上限比原始的基于路径的框架提供了更好的上限：此外，我们通过捆绑并在$ o（m + n \ log n）$时间中捆绑并绘制DAG的所有边缘，使用最小额外的宽度来扩展此框架。我们还提供了与众所周知的层次绘图框架（广泛称为Sugiyama框架）作为概念证明的比较。实验结果表明，我们的算法产生的图纸在弯曲面积和弯曲数方面较好，但对于稀疏图的穿越较差。因此，我们的技术为绘制分层图提供了有趣的替代方法。最后，我们提出了一个$ O（M + K \ log K）$ TIME算法，该算法计算路径的特定顺序，以减少总边长度以及交叉和弯曲的数量。
We present algorithms that extend the path-based hierarchical drawing framework and give experimental results. Our algorithms run in $O(km)$ time, where $k$ is the number of paths and $m$ is the number of edges of the graph, and provide better upper bounds than the original path based framework: e.g., the height of the resulting drawings is equal to the length of the longest path of $G$, instead of $n-1$, where $n$ is the number of nodes. Additionally, we extend this framework, by bundling and drawing all the edges of the DAG in $O(m + n \log n)$ time, using minimum extra width per path. We also provide some comparison to a well known hierarchical drawing framework, widely known as the Sugiyama framework, as a proof of concept. The experimental results show that our algorithms produce drawings that are better in area and number of bends, but worse for crossings in sparse graphs. Hence, our technique offers an interesting alternative for drawing hierarchical graphs. Finally, we present an $O(m + k \log k)$ time algorithm that computes a specific order of the paths in order to reduce the total edge length and number of crossings and bends.
