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.

  • 1
    $\begingroup$ I once did a search for this, and could not find anything. Note that this is a hard problem and likely only feasible for tiny graphs! There's a Mathematica Journal article, but it only discusses a few special cases. mathematica-journal.com/2009/11/crossing-number-graphs GraphData does 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:13
  • $\begingroup$ IGraph/M has the IGSmoothen function 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

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.

| improve this answer | |
  • $\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
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.