Here, you can find the code, instances, data, and additional plots for 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
The different crossing minimization heuristics can be found as part of the following OGDF classes:
|Abbrev.||Long Name (in paper)||C++-Class|
|ccm||Chordless Cycle Method||
|mim||Mixed Insertion Method||
|srm||Star Reinsertion Method||
For more documentation, see here.
For an example of their usage, note that the classes are used as part of the test in
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.