I have been searching for a mathematica package that can calculate the graph Crossing number of a (small) given arbitrary graph (the graphdata of known graphs doesn't help me). Before I write my own I'm checking here. My google searches returned methods to calculate it (or variants of the question) but didn't find any real implementation.
$\begingroup$
$\endgroup$
3
asked Jan 17 '19 at 17:04
$\begingroup$
$\endgroup$
2
Geoffrey Exoo wrote code for finding (rectilinear) crossing numbers of arbitrary (small enough) graphs. I asked him last year about the possibility of reviving it from whatever retired hardware (floppies) it lives on. Unfortunately, I gather any such efforts have not (yet?) been successful.
-
1$\begingroup$ For such hard problems, the most fruitful approach is often to map them into integer programming. There are multiple papers on how to do this for crossing numbers and Mathematica already has a good ILP solver. Have you looked into this? (BTW the same approach worked very well for graph colouring—map it into SAT and solve using Mathematica. Did you get my MathWorld feedback email on this?) $\endgroup$ – Szabolcs Jan 17 '19 at 17:39
-
1$\begingroup$ I'd love to see this implemented in M: ls11-www.cs.tu-dortmund.de/people/chimani/files/… If anyone succeeds, please contact me. $\endgroup$ – Szabolcs Jan 17 '19 at 17:43
GraphDatadoes not implement any algorithm for this, it's only a database of pre-computed properties. If your graph of interest is not in it, you're out of luck. $\endgroup$ – Szabolcs Jan 17 '19 at 17:13IGSmoothenfunction which you may find useful: it eliminates all degree-2 vertices, creating a smaller graph with the same crossing number. Sage has a (very inefficient) crossing number implementation. You may look for inspiration in the discussion around that: trac.sagemath.org/ticket/24216 Finally, if you do implement something yourself, consider contributing it to IGraph/M. $\endgroup$ – Szabolcs Jan 17 '19 at 17:21