Overview

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:

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 us: Markus Chimani or Tilo Wiedera.

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.
  6. 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.