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

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

• Code: GitHub or OGDF website
• Instances: crossing_number_instances.zip
• Data: star_struck_data.zip
• Additional Plots: star_struck_additional_plots.pdf

The different crossing minimization heuristics can be found as part of the following OGDF classes:

Parameters:

• plm: To set the planar subgraph algorithm and the edge insertion algorithm, use setInserter() and setSubgraph() respectively.
• mim: To set the strategy by which mim chooses stars to insert, use nodeSelectionMethod().
• srm: To set the algorithm that creates the initial planarization, use setPlanarization().

For more documentation, see here. For an example of their usage, note that the classes are used as part of the test in test/src/planarity/crossing-minimizer.cpp.

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.