4
$\begingroup$

The case for $\operatorname{cr}(G)=0$ (planar graphs) is given by Wagner's theorem, but what about (for instance) the family of graphs with $\operatorname{cr}(G) \leq 1$?

1 Answers 1

2

Check out this link. It claims that the family of graphs with crossing number $\leq k$ is not minor-closed for general $k$, though I don't understand the example there. One can fix the definition so that it be minor-closed by "blatantly" enforcing it, see here. Of course, once we have a minor-closed family, Robertson-Seymour theory tells us that there is a finite list of forbidden minors.

  • 0
    Very helpful, thank you. I understand the argument given in the first link for the claim that $cr(G/e) \nleq cr(G)$ in general, which means that the families I described are not minor-closed.2011-09-10