This program aims to validate the correctness of crossing numbers.
Given a graph G and a set of Kuratowski subdivisions it can be shown that the crossing number of G exceeds some lower bound using linear programming.
Existing algorithms are able to identify a small subset of the exponentially large set of Kuratowski subdivisions, such that the bound grows tight.
However, all implementations lack the required readability to comprehend the supposed proof.
The validator will be used to track down bugs in the existing implementations and to validate generated proofs. Sufficient readability is a major objective.
You need one of the following linear program solvers available on your command line:
gurobi_cl(http://www.gurobi.com)scip(http://scip.zib.de)cplex
Java Runtime Environment 7 or higher is required to run the program.
This program is part of a master thesis developed at Osnabrück University (Algorithm Engineering group). The Open Graph Drawing Framework is utilized for extracting the set of Kuratowski subdivions. My work is based on Computing Crossing Numbers PhD Thesis by M. Chimani, Technical University Dortmund, 2008 and A New Approach to Exact Crossing Minimization by M. Chimani, P. Mutzel, I. Bomze, 16th Annual European Symposium on Algorithms 2008, Karlsruhe (ESA08), LNCS 5193, pp. 284-296, Springer, 2008.
Copyright (c) 2015 Tilo Wiedera
This program is released under the MIT License.