8
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\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
    Commented Jan 17, 2019 at 17:13
  • 1
    $\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
    Commented Jan 17, 2019 at 17:21
  • 1
    $\begingroup$ @Szabolcs When I read some progress of crossing number. I found such an online tool, which seems to be great, but I am not very good at using it. crossings.uos.de $\endgroup$
    – licheng
    Commented Mar 6, 2021 at 12:56

2 Answers 2

Reset to default
4
$\begingroup$

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
$\endgroup$
2
  • 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
    Commented Jan 17, 2019 at 17:39
  • 2
    $\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
    Commented Jan 17, 2019 at 17:43
3
$\begingroup$

There are some C or Java programs available for computing crossing number, but not in wolfram language. But we can call it. One of them is QuickCross.

Import["!D://QuickCross//QC -g I~qkzXZLw", "Table"]
                      (*{{"CR", ":", 12}}*)

This is a bit like Mathematica calling nauty-geng's results.

If one wishes to actually solve instances, Markus Chimani and Tilo Wiedera produced a mixed-integer linear program in 2016 that is able to compute crossing numbers for small graphs, complete with a proof file, and produced an online interface, Crossing Number Web Compute , where researchers can submit their owninstances.

The crossing number results of specific graphs can be referred to in the following review.

  • Clancy K, Haythorpe M, Newcombe A. A survey of graphs with known or bounded crossing numbers[J]. arXiv preprint arXiv:1901.05155, 2019.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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