The function crossing_number runs too slowly?
In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them.
The exact and non-heuristic programs that I know of are the following:
- sagemath
- web crossing number (http://crossings.uos.de/) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.
- OGDF (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)
I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.
Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.
G = graphs.GrotzschGraph()
G.crossing_number()It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?
Indeed, we only have a slow brute force implementation. Help implementing a faster algorithm is more than welcome.
Thanks! Maybe it's because the program was interrupted on my computer. I recomputed it, and it took me about three hours and sagemath gives me the correct result "5". As for any improvement, it should be something we love.
@David Coudert A drawing D is optimal if it realizes cr(D) = cr(G). Another interesting question is, can the crossing_number or other function give an optimal drawing of G.
What precisely is the question here? Comments about possible ways to improve Sage are welcome, but I don't see a question.
I guess the question is how to improve the situation (see the last sentence).