Algorithms for the Hypergraph and the Minor Crossing Number Problems

Abstract

We consider the problems of hypergraph and minor crossing minimization, and point out relationships between these two problems that have not been exploited before. In the first part of this paper, we present new complexity results regarding the corresponding edge and vertex insertion problems. Based thereon, we present the first planarization-based heuristics for hypergraph and minor crossing minimization. Furthermore, we show how to apply these techniques to hypergraphs arising in real-world electrical circuits. The experiments in this paper show the applicability and strength of this planarization approach, considering established benchmark sets from electrical network design. In particular, we show that our heuristics lead to roughly 40-70% less crossings compared to the state-of-the-art algorithms for drawing electrical circuits.