Optimal k-Level Planarization and Crossing Minimization

Gange, Graeme and Stuckey, Peter J. and Marriott, Kim (2011) Optimal k-Level Planarization and Crossing Minimization. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010 , pp. 238-249(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_22).

Full text not available from this repository.


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 find optimal orderings 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_22
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.840 Planarization
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1210

Actions (login required)

View Item View Item