Algorithms for the hypergraph and the minor crossing number problems

Autor(en): Chimani, M. 
Gutwenger, C.
Erscheinungsdatum: 2015
Herausgeber: Brown University
Enthalten in: Journal of Graph Algorithms and Applications
Band: 19
Ausgabe: 1
Startseite: 191
Seitenende: 222
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. © 2015, Brown University. All rights reserved.
ISSN: 15261719
DOI: 10.7155/jgaa.00353
Externe URL:

Show full item record

Page view(s)

Last Week
Last month
checked on Jun 15, 2024

Google ScholarTM