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$
2
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.
-
$\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
Not the answer you're looking for? Browse other questions tagged graphs-and-networks packages algorithm or ask your own question.
Hot Network Questions
- Why is the normal distribution used in linear models, but in generalized linear models the exponential distribution is used? Detailed answer
- How did the Menorah of pure gold remain standing?
- What's the difference between declaring sovereignty and declaring independence?
- What is this flag with a red 6-pointed star in a red crescent on white ground?
- Carry on baggage allowance - Confused about these sizes
- Generalise perfect numbers
- Excel: find the nearest (to a reference one) date for each row
- Can fundamental analysis be applied to market indexes as if they were single stocks/bonds?
- How to test the lifespan of electrical components?
- Why does Samsung company name means "Three stars" and not "Three castle"?
- Merging material slots?
- Multiple conditions for a while loop
- How strong is a chain link? How about half a chain link?
- What does "Bool-var" mean in "In the Midst of Alarms"?
- Connecting flights - How does ticket and boarding work?
- Curiosity and Perseverance landing - with so much dust blown everywhere, what's the point of the skycrane?
- Does C or C++ guarantee array < array + SIZE?
- What is the opposite of 'owe'?
- Is Perseverance unable to move?
- Why don’t airplanes use turn signals?
- Is it safe to add garlic powder to sesame oil?
- How is this a checkmate?
- How can I run newer Unity games on OS X 10.9 Mavericks?
- How can I help one of my players be more tanky?
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