Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

User Tools


Crossing Number

WebCompute Instances

Here, you can find a collection of graphs uploaded to the crossing number web service. All graphs are provided in GML format (see upward planarity for details).

Year Version # Graphs Link
2020 non-planar, some obvious duplicates removed 510 instances-2020.tar.gz (128KB)
2015 non-planar, solved 145 instances-2015.tar.gz (70KB)
2015 all (including some planar submissions) 222 instances-2015-all.tar.gz (93KB)

Crossing Number Heuristics (Star Insertion): Data and Instances

Here, you can find the instances and data used by the evaluation presented in the following paper:

Markus Chimani, Max Ilsen, and Tilo Wiedera: "Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics", GD 2021, extended version available at https://arxiv.org/abs/2108.11443

Rome Graphs: Exact Crossing Numbers

rome_cr.zip contains a table with the crossing number for each of the Rome graphs. If the crossing number could not be computed due to a time limit or an algorithm error, the crossing number is replaced by the string "Aborted" or "Error" respectively.

rome_proofs.zip contains the proofs for the crossing numbers, see http://crossings.uos.de/ for more information on how these proofs are created and how to validate them. The graph described in a proof file is the non-planar core of the respective instance. The proof file is empty iff the algorithm was not able to compute the crossing number.

We do not guarantee the correctness of these results. Please validate the proofs of the graphs that interest you in order to make sure that the respective crossing number is correct.

research/cr.txt · Last modified: September 27, 2021 (21:22) by ilsen