A New Approach to Exact Crossing Minimization
From MaRDI portal
Publication:3541091
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
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