Layered graph drawing
Layered graph drawing
复制标题
分层图形绘制
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Suderman
中科院分区：
文献类型：
--
作者：
M. Suderman
分层图是组合图的二维图，其中顶点位于给定的一组水平线上。这些图纸用于软件工程、生物信息学和VLSI设计等应用领域。除了被分层之外，这些应用中的绘图还可以满足其他约束，例如边缘交叉的数量上的界限。与获得这些图纸有关的问题几乎总是NP -困难的，所以，在这篇论文中，我们研究这些问题的限制版本，以找到有效的算法解决方案，可以在实践中使用。
作为第一个非常严格的限制，我们考虑平面的分层绘图。然而，即使有了这个限制，所产生的问题仍然是NP难的.除了证明这样的硬度结果，我们成功地推导出两个问题的有效算法。在这两种情况下，我们纠正了以前发表的结果，声称这些问题的算法非常简单和有效的解决方案。我们的解决方案，虽然也很有效，但表明这些问题的真相比发表的结果要复杂得多。
我们还研究了非平面分层绘图，特别是通过交叉最小化和最小平面化获得的绘图。虽然相应的问题是NP困难的，但当要最小化的值是一个常数的上界时，它们变得容易处理。这种获得易处理问题的方法在一种称为参数化复杂性的理论中被形式化，由此产生的易处理问题和算法解决方案被称为固定参数易处理（FPT）。虽然相对较新，这个理论已经吸引了理论成果的快速增长。事实上，我们得出了最著名的渐进运行时间平面化在两层图纸原始FPT算法。
由于参数化复杂性是如此的新，很少有人知道它对图形绘制实践的影响。因此，我们已经实现了一些FPT算法，并将它们与以前实现的方法，特别是整数线性规划（ILP）进行了实验比较。我们的实验表明，我们的FPT平面化算法的性能是有竞争力的，目前的ILP算法，但交叉最小化，目前的ILP算法仍然是明显的赢家。
A layered graph drawing is a two-dimensional drawing of a combinatorial graph in which the vertices lie on a given set of horizontal lines. Such drawings are used in application domains such as software engineering, bioinformatics, and VLSI design. In addition to being layered, drawings in these applications may also satisfy other constraints, for example bounds on the number of edge crossings. The problems related to obtaining these drawings are almost always NP -hard, so, in this thesis, we investigate restricted versions of these problems in order to find efficient algorithmic solutions that can be used in practice.
As a first very drastic restriction, we consider layered drawings that are planar. Even with this restriction, however, the resulting problems can still be NP -hard. In addition to proving one such hardness result, we do succeed in deriving efficient algorithms for two problems. In both cases, we correct previously published results that claimed extremely simple and efficient algorithmic solutions to these problems. Our solutions, though efficient as well, show that the truth about these problems is significantly more complex than the published results would suggest.
We also study non-planar layered drawings, particularly drawings obtained by crossing minimization and minimum planarization. Though the corresponding problems are NP -hard, they become tractable when the value to be minimized is upper-bounded by a constant. This approach to obtaining tractable problems is formalized in a theory called parameterized complexity, and the resulting tractable problems and algorithmic solutions are said to be fixed-parameter tractable ( FPT ). Though relatively new, this theory has attracted a rapidly growing body of theoretical results. Indeed, we derive original FPT algorithms with the best-known asymptotic running times for planarization in two layer drawings.
Because parameterized complexity is so new, little is known about its implications to the practice of graph drawing. Consequently, we have implemented a few FPT algorithms and compared them experimentally with previously implemented approaches, especially integer linear programming (ILP). Our experiments show that the performance of our FPT planarization algorithms are competitive with current ILP algorithms, but that, for crossing minimization, current ILP algorithms remain the clear winners.