Overview

This tool computes (or at least tries to compute) the exact crossing number of a given undirected graph. The algorithm uses an ILP formulation—based on Kuratowski subgraphs and linear orderings—and solves it via branch-and-cut-and-price. It was described in [1] and [2]. Further information on this approach (or its predecessors) can be found in [3,4,5].

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. – If you use this tool for whatever purpose, I would be very happy to hear from you! And if your use the obtained results in scientific work, we all love being notified and cited, aren't we?

You may request a computation of the crossing number for any reasonably large graph here.

Formal Proof of Correctness

The computed planarized drawing of each biconnected component constitutes an upper bound on the respective crossing number. To comprehend the lower bound a proof file is extracted that contains a description of the linear programs used internally to prove the optimality of the drawing. Since the proof file contains all required Kuratowski subdivisions it is rather large. A standalone application reviews the proof for the lower bound and confirms the correctness. A paper that explains the validation procedure in detail will be published soon.

Overall, I haven't experienced wrong result for years, neither did colleagues. I usually run two competing, independent implementations side by side, one for each of the known ILP formulations [1]

A Note on the Code and Setup

The code is a derivative of the one discussed in [1]. It 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 [1]. In fact, the running times obtained via this web tool are likely to be clearly slower:

Instances

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

Contact

For further questions, problems etc. feel free to contact me: Markus Chimani.

Bibliography

[1] 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.
[2] M. Chimani. Computing Crossing Numbers. PhD Thesis, Technical University Dortmund, 2008.
[3] M. Chimani. Facets in the Crossing Number Polytope. SIAM Journal on Discrete Mathematics, Vol. 25(1), pp. 95-111, SIAM, 2011.
[4] 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.
[5] 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.