Algorithms for the Hypergraph and the Minor Crossing Number Problems
Markus Chimani and Carsten Gutwenger
Vol. 19, no. 1, pp. 191-222, 2015. Regular paper.
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.
Submitted: January 2014.
Reviewed: April 2014.
Revised: July 2014.
Reviewed: September 2014.
Revised: January 2015.
Accepted: March 2015.
Final: March 2015.
Published: March 2015.
Communicated by Seok-Hee Hong
article (PDF)