Suppose we are given a regular dodecahedron. Then we add five crossed edges inside each of its faces (actually, inside each face it is a copy of $K_5$). It is clear that this drawing has 60 crossings. My question now is whether such a graph has crossing number 60? How to prove or disprove it?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ There appears to be an implementation of an integer programming formulation that has worked on graphs of roughly the same size as yours: sciencedirect.com/science/article/pii/S1572528607000497#sec5 . You could try that to see if your conjecture is true. (The approach of Noam Elkies in the previous question only seems to yield that the crossing number is at least 36, unless I made a calculation error.) $\endgroup$– Elle NajtCommented Nov 8, 2020 at 8:51
-
3$\begingroup$ There are better bounds, because we know that if a graph has >4n-8 edges, then one of them has at least two crossings; see J. Pach and G. Toth, Graphs drawn with few crossings per edge. This gives that at least 18 of the edges have at least two crossings, a further 18 at least one, resulting in a lower bound of 54. $\endgroup$– domotorpCommented Nov 11, 2020 at 9:07
Add a comment
|