Optimal k-Level Planarization and Crossing Minimization
Optimal k-Level Planarization and Crossing Minimization
复制标题
DOI：
10.1007/978-3-642-18469-7_22
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
G. Gange;Peter James Stuckey;K. Marriott
中科院分区：
文献类型：
--
作者：
G. Gange;Peter James Stuckey;K. Marriott
布局分层网络图的一个重要步骤是对每一层上的节点进行排序。通常的方法是尽量减少边缘交叉的数量。当第一层固定时，即使对于两层，该问题也是NP难的。因此，在实践中，交叉最小化是使用遗传算法来执行的。另一种建议的方法是最大化平面子图，即找到要删除的最少数量的边以使图平面。同样，这是使用几何学来执行的，因为平面性的最小边缘删除是NP难的。我们表明，使用现代SAT和MIP求解方法，我们可以找到最小交叉或最小边删除的最佳顺序，以在合理大小的图上实现平面化。这些精确的方法提供了一个衡量启发式交叉最小化和平面化算法的质量的基准。此外，我们可以直接扩展我们的方法，以最大限度地减少交叉，其次是最大化平面子图，反之亦然，这些混合方法产生明显更好的布局，然后单独交叉最小化或平面化。
An important step in laying out hierarchical network diagrams is to order the nodes on each level. The usual approach is to minimize the number of edge crossings. This problem is NP-hard even for two layers when the first layer is fixed. Hence, in practice crossing minimization is performed using heuristics. Another suggested approach is to maximize the planar subgraph, i.e. find the least number of edges to delete to make the graph planar. Again this is performed using heuristics since minimal edge deletion for planarity is NP-hard. We show that using modern SAT and MIP solving approaches we can findoptimalorderings for minimal crossing or minimal edge deletion for planarization on reasonably sized graphs. These exact approaches provide a benchmark for measuring quality of heuristic crossing minimization and planarization algorithms. Furthermore, we can straightforwardly extend our approach to minimize crossings followed by maximizing planar subgraph or vice versa; these hybrid approaches produce noticeably better layout then either crossing minimization or planarization alone.