This tool computes (or at least tries to compute) the exact crossing number of a given undirected graph.
You may use the tool not only to find the crossing number of some interesting graph,
but also to validate (assumed) proofs of not-too-large graphs,
or to test or come up with crossing number hypotheses of interesting graph classes.
The algorithm uses an ILP formulation—based on Kuratowski subgraphs—and solves it via branch-and-cut-and-price.
It is based on the approaches described in [1-5].
Furthermore, the system available here generates verifiable formal proofs, as described in [6].
A standalone proof verifier can be downloaded here.
Please request a computation of the crossing number for any reasonably large graph here.
Citations
We kindly ask you to cite [6] in any publications that you use this service for.
You may additionally supply a link to any computation as the generated tokens will remain valid indefinitely.
A Note on the Code and Setup
The algorithm is implemented as part of the free (GPL)
Open Graph Drawing Framework (OGDF)
and uses the free (LGPL) Abacus
branch-and-cut-and-price framework.
Abacus itself uses the free Coin-OR infrastructure to communicate with a backend LP-solver.
However, the obtained running times cannot directly be compared with, e.g., [1].
In fact, the running times obtained via this web tool are likely to be clearly slower:
We are using two independent ILP formulations, the latter augmented with proof extraction as described in [6].
Additionally, the proof verification procedure is run after each extraction.
Due to licencing restrictions, this tool does not use CPLEX as its LP-solver backend,
but the free (albeit slower) alternative CLP.
This web service runs on a virtual machine somewhere in our server rack. We apply a memory limit of 1 GB.
The algorithms allow a lot of parameter tuning
(e.g., number of runs of the initial upper bound heuristics, branching strategies, etc.).
Since the tool cannot assume anything about the given graphs, a very conservative parameter setting was chosen.
Instances
We are periodically collecting the set of graphs uploaded to this service to be used for benchmarks.
M. Chimani, P. Mutzel, I. Bomze. A New Approach to Exact Crossing Minimization.
16th Annual European Symposium on Algorithms 2008, Karlsruhe (ESA08), LNCS 5193, pp. 284-296, Springer, 2008.
M. Chimani. Computing Crossing Numbers. PhD Thesis, Technical University Dortmund, 2008.
M. Chimani. Facets in the Crossing Number Polytope.
SIAM Journal on Discrete Mathematics, Vol. 25(1), pp. 95-111, SIAM, 2011.
M. Chimani, C. Gutwenger, P. Mutzel. Experiments on Exact Crossing Minimization using Column Generation.
ACM Journal of Experimental Algorithmics, Vol. 14(3), pp. 4.1-4.18, 2009.
C. Buchheim, M. Chimani, D. Ebner, C. Gutwenger, M. Jünger, G.W. Klau, P. Mutzel, R. Weiskircher.
A Branch-and-Cut Approach to the Crossing Number Problem. Discrete Optimization, Vol. 5(2),
Special Issue in Memory of George B. Dantzig, pp. 373-388, 2008.