A New Approach to Exact Crossing Minimization

DOI10.1007/978-3-540-87744-8_24zbMath1158.90423OpenAlexW1607613323MaRDI QIDQ3541091

Petra Mutzel, Markus Chimani, Immanuel M. Bomze

Publication date: 25 November 2008

Published in: Algorithms - ESA 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87744-8_24

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics ⋮ Recent Advances in Exact Crossing Minimization (Extended Abstract) ⋮ Star-struck by fixed embeddings: modern crossing number heuristics ⋮ Planar crossing numbers of graphs of bounded genus ⋮ Vertex insertion approximates the crossing number of apex graphs ⋮ On the crossing numbers of Cartesian products of wheels and trees ⋮ Crossing numbers of beyond-planar graphs ⋮ Crossing numbers of beyond-planar graphs ⋮ Advances in the Planarization Method: Effective Multiple Edge Insertions ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ 1-planarity testing and embedding: an experimental study ⋮ The crossing numbers of join of special disconnected graph on five vertices with discrete graphs

Cites Work

• Unnamed Item
• A branch-and-cut approach to the crossing number problem
• String graphs. II: Recognizing string graphs is NP-hard
• A note on the parity of the number of crossings of a graph
• Inserting an edge into a planar graph
• Which crossing number is it anyway?
• An experimental comparison of four graph drawing algorithms.
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Bimodal Crossing Minimization
• Graph Drawing
• Experiments on Exact Crossing Minimization Using Column Generation
• Algorithms for the Hypergraph and the Minor Crossing Number Problems
• Efficient Extraction of Multiple Kuratowski Subdivisions
• The crossing number of K5,n
• Graph Drawing
• Recognizing string graphs in NP