Algorithms for the hypergraph and the minor crossing number problems

DC FieldValueLanguage
dc.contributor.authorChimani, M.
dc.contributor.authorGutwenger, C.
dc.date.accessioned2021-12-23T16:32:28Z-
dc.date.available2021-12-23T16:32:28Z-
dc.date.issued2015
dc.identifier.issn15261719
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17371-
dc.description.abstractWe 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.
dc.language.isoen
dc.publisherBrown University
dc.relation.ispartofJournal of Graph Algorithms and Applications
dc.titleAlgorithms for the hypergraph and the minor crossing number problems
dc.typejournal article
dc.identifier.doi10.7155/jgaa.00353
dc.identifier.scopus2-s2.0-84982193686
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84982193686&doi=10.7155%2fjgaa.00353&partnerID=40&md5=94eabc264329905f3146ed1dae830448
dc.description.volume19
dc.description.issue1
dc.description.startpage191
dc.description.endpage222
dcterms.isPartOf.abbreviationJ. Graph Algorithms and Appl.
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

5
Last Week
0
Last month
1
checked on May 27, 2024

Google ScholarTM

Check

Altmetric