# Theoretical Computer Science / Theoretische Informatik

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

research:cr

# 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

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() 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 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: 2022/04/27 16:44 by ilsen