3
$\begingroup$

How would one go about proving that the crossing number for a graph is the lowest possible?

To be more specific, given a specific representation of a particular cubic graph $G$, how do I prove that the crossing number can not be lowered any further?

This $G$ has $|V|<20$, and $\operatorname{cr}{(G)}\geq 2$. Furthermore, various online sources say the $\operatorname{cr}{(G)}$ I have found is correct, but offer no proof of why.

Complexity for this in general is hard, supposedly NP-hard, and no general solution is known, but given that the number of vertices is small enough and graph is 3-regular, there must be a way.

$\endgroup$
2
  • 1
    $\begingroup$ Why do you think these restrictions are enough to get an easy solution? Wikipedia says that the problem remains NP-hard when restricted to 3-regular graphs. In this particular case it might be feasible that simply show that there's no edge such that removing it makes the graph planar, just by showing that each of the edges is avoided by some forbidden subgraph. $\endgroup$
    – hmakholm left over Monica
    Dec 2, 2011 at 12:16
  • $\begingroup$ I do not think that there is an easy solution. Idea about the forbidden subgraph is a good one, you just gave me inspiration if I could show that that one still has a K3,3 subgraph(K5 is not happening) no matter what edge is removed would be one way. $\endgroup$
    – Sint
    Dec 5, 2011 at 13:00

2 Answers 2

Reset to default
2
$\begingroup$

Geoff Exoo has a good program that works well for small graphs. I worked with him for identifying what we called the Crossing Number Graphs, which attain some high crossing number.

Initially, Geoff's program optimizes some random embedding. 99.9% of the time, it will find some reasonably good crossing. We were looking for the graphs with highest crossing number, so any that had something lower, we would discard.

For 22 vertex cubic graphs, we were left with 4 graphs that the "fast" program said had 7 crossings. Geoff also had a "slow" program, that would study a single graph for something like 10 hours. I also looked at each of these graphs extensively by hand, and subsequently many others have as well.

Post the graph, and I can take a look at it.

$\endgroup$
1
$\begingroup$

If the graph is small enough and you were willing to prove it by hand, you could do a case analysis similar to how students show a graph is non-planar ($cr(G) \geq 1$) by hand.

Take a long cycle (hopefully Hamiltonian), and place it evenly spaced on a circle, then start adding in edges. You're done if you can show by case analysis that no matter how the edges are added, more than one crossing is created.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .