Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings.

Is the list of obstructions to being able to embed a graph with no edge-crossings on the surface of genus $g$ known to be finite for all $g$?

  • 2
    $\begingroup$ "planar graphs on surfaces of genus $g$" isn't really what you mean, is it? Maybe change the title to something more like what's in the body, something like, "obstructions to embedding graphs in surfaces of genus $g$"? $\endgroup$ – Gerry Myerson Nov 19 '10 at 22:04
  • 5
    $\begingroup$ @Dr Shello: If you think TonyH's answer is correct, it would be good to formally accept it (by clicking the checkmark). $\endgroup$ – Sheikraisinrollbank Dec 8 '10 at 14:24
  • $\begingroup$ The surename of famous mathematician was: KURATOWSKI. $\endgroup$ – kakaz Dec 6 '15 at 19:42

I'll just remark that the fact that every surface has a finite number of excluded minors (and also topological minors) does not require the full strength of the Graph Minors Theorem. Indeed, the proof relies on the following three facts:

  1. The Grid Theorem. There exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph with tree-width at least $f(n)$, contains the $n \times n$ grid as a minor.

  2. Graphs of bounded tree-width are well-quasi-ordered. For any $k$, the class of graphs of tree-width at most $k$ is well-quasi-ordered.

  3. Forbidden minors for surfaces do not contain arbitrarily large grid minors. There is a function $h: \mathbb{N} \to \mathbb{N}$, such that every minor-minimal graph not embeddable on a surface of genus $g$ does not contain an $h(g) \times h(g)$ grid as a minor.

All three of these facts now have very compact proofs. In fact, proofs for (1) and (3), and a sketch of a proof of (2) can be found in Diestel's Graph Theory textbook. See here to peruse the book online.

  • 1
    $\begingroup$ Awesome, this is exactly what I was looking for, thx. $\endgroup$ – Dr Shello Nov 19 '10 at 18:45

Yes. Wagner's Conjecture/Robertson and Seymour's Theorem says that any graph family closed under taking minors can be defined by specifying a finite list of forbidden minors. For any surface $S$, the graphs embeddable $S$ without crossing edges forms a family closed under taking minors.

I haven't looked carefully at it but Jim Belk's introduction to graph minor theory seems good. On the linked page he mentions the following facts: the projective plane has 35 forbidden minors, the number for the torus is in the hundreds thousands (at least, the precise number/collection is not known), and in general the number of forbidden minors grows exponentially with the genus.

  • 10
    $\begingroup$ In fact, for the torus there are more than 16,000 known forbidden minors! (See arxiv.org/abs/math/0411488 .) $\endgroup$ – José Figueroa-O'Farrill Nov 19 '10 at 18:07
  • 3
    $\begingroup$ Which begs the question: why do 2 forbidden minors are enough in the plane? I mean, why so few? $\endgroup$ – Ori Gurel-Gurevich Nov 19 '10 at 18:49
  • 1
    $\begingroup$ What's the approx number for genus 2? $\endgroup$ – Dr Shello Nov 20 '10 at 5:26

For the projective plane, i.e. the nonorientable surface of genus 1, this is known. Look at "A Kuratowski Theorem for the Projective Plane" in the homepage of Dan Archdeacon here: http://www.emba.uvm.edu/~archdeac/ This was his PhD thesis. In particular, he found that there are exactly 103 graphs such that if any graph $G$ contains one of these graphs as a subgraph, then $G$ cannot be not embedded into projective plane. You can refer to his original thesis for the list of the 103 graphs, or you can refer to the Appendix A of the book "Graphs on Surfaces" by Bojan Mohar and Carsten Thomassen.

  • 4
    $\begingroup$ Minor (no pun intended) remark: a graph is embeddable on the projective plane if and only if it does not contain a subdivision of one of the 103 said graphs. The excluded minors for the projective plane are also known; there are 35 of them. $\endgroup$ – Tony Huynh May 18 '11 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.