Given a graph, the Crossing Number Problem asks for the drawing of that graph in a plane such that the number of edge crossings is minimised. This problem has been widely studied since it was first posed in the 1950 by Turán. If you want to learn more about the problem and the current state of research into it, a recent book, “Crossing Numbers of Graphs” by Marcus Schaefer was published in 2018 and is an excellent read.
Our heuristic, QuickCross, is designed to find optimal or near-optimal embeddings of graphs. Source code is available in both C and MATLAB. It is free to use for academic purposes. We only ask that if you use it, that you kindly cite our paper in which we describe the algorithm:
K. Clancy, M. Haythorpe, A. Newcombe. “An effective crossing minimisation heuristic baesd on star insertion.” Journal of Graph Algorithms and Applications, submitted 2018. Available at: http://arxiv.org/abs/1804.09900
If you would like to discuss using QuickCross for commercial or government purposes, please contact Michael Haythorpe.
QuickCross works by starting with a (most likely suboptimal) initial embedding of the graph, and then looking to iteratively improve the embeddings by moving one vertex at a time. Experiments show that the algorithm is particularly effective on dense graphs, and is very efficient to run.
QuickCross allows you to submit any graph, or a collection of graphs (in graph6 format) and it will attempt to find a good embedding. You have quite a bit of flexibility in terms of how the initial embedding is found (including simply submitting your own initial embedding), and also how improvements are discovered.
If you have any questions, or to report any bugs, please contact Michael Haythorpe.
QuickCross: Download (349kb) – Updated Nov 28th 2018. Contains both MATLAB and C implementations, as well as a pre-compiled Windows executable file.
QuickCross was also used to prove a conjecture by Ed Pegg Jr and Geoffrey Exoo that the Coxeter graph is a minimal example of a cubic graph with 11 crossings. The details can be found in the following paper:
M. Haythorpe and A. Newcombe. “There are no Cubic Graphs on 26 Vertices with Crossing Number 11.” Journal of Graph Theory, submitted 2018. Available at: http://arxiv.org/abs/1804.10336