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.

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.

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.

We are periodically collecting the set of graphs uploaded to this service to be used for benchmarks.

For further questions, problems etc. feel free to contact us: Markus Chimani or Tilo Wiedera.

- 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.
- M. Chimani, T. Wiedera. An ILP-based Proof System for the Crossing Number Problem. 24th European Symposium of Algorithms (ESA) 2016, Aarhus, Denmark, LIPIcs, to appear.