A branch-and-cut approach to the crossing number problem
From MaRDI portal
Publication:951113
DOI10.1016/j.disopt.2007.05.006zbMath1146.05017OpenAlexW2101447138WikidataQ56977220 ScholiaQ56977220MaRDI QIDQ951113
Christoph Buchheim, Michael Jünger, Carsten Gutwenger, Petra Mutzel, Gunnar W. Klau, Dietmar Ebner, René Weiskircher, Markus Chimani
Publication date: 29 October 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2007.05.006
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, A New Approach to Exact Crossing Minimization, On the crossing numbers of Cartesian products of wheels and trees, Non-planar core reduction of graphs, The Crossing Number of Graphs: Theory and Computation, Iterative Refinement for Linear Programming, The crossing numbers of join of special disconnected graph on five vertices with discrete graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A framework for solving VLSI graph layout problems
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- String graphs. II: Recognizing string graphs is NP-hard
- Computing an st-numbering
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Graphs drawn with few crossings per edge
- Edge crossings in drawings of bipartite graphs
- Inserting an edge into a planar graph
- On-line maintenance of triconnected components with SPQR-trees
- Maximum planar subgraphs and nice embeddings: Practical layout tools
- An experimental comparison of four graph drawing algorithms.
- Alpha-algorithms for incremental planarity testing (preliminary version)
- Decomposition Principle for Linear Programs
- Crossing Number is NP-Complete
- On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
- Efficient Planarity Testing
- A Better Approximation Algorithm for Finding Planar Subgraphs
- An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
- On Cotree-Critical and DFS Cotree-Critical Graphs
- On-Line Planarity Testing
- The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
- A linear algorithm for the maximal planar subgraph problem
- Computing crossing numbers in quadratic time
- Graph Drawing
- Crossing minimization in linear embeddings of graphs
- Improved Bounds for the Crossing Numbers of Km,n and Kn
- Fundamentals of Computation Theory
- Integer Programming and Combinatorial Optimization
- Computing and Combinatorics
- Graph Drawing
