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.

  • 1
    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.2011-12-02
  • 0
    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.2011-12-05

2 Answers 2