A branch-and-cut approach to the crossing number problem

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

zbMATH Keywords

column generationcrossing numberbranch-and-cut

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, 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

• ABACUS
• OGDF
• PIGALE

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