Optimal k-level planarization and crossing minimization

Abstract

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 reason..