Table of Contents
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): Code, Instances, Data, Plots
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:
| Abbrev. | Long Name (in paper) | C++-Class |
|---|---|---|
| plm | Planarization Method | SubgraphPlanarizer |
| ccm | Chordless Cycle Method | PlanarizerChordlessCycle |
| mim | Mixed Insertion Method | PlanarizerMixedInsertion |
| srm | Star Reinsertion Method | PlanarizerStarReinsertion |
Parameters:
- plm: To set the planar subgraph algorithm and the edge insertion algorithm, use
setInserter()andsetSubgraph()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 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 crossing number web service 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.