Obstructions for embedding a graph on a surface of genus g

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$?

• "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$"? – Gerry Myerson Nov 19 '10 at 22:04
• @Dr Shello: If you think TonyH's answer is correct, it would be good to formally accept it (by clicking the checkmark). – Sheikraisinrollbank Dec 8 '10 at 14:24
• The surename of famous mathematician was: KURATOWSKI. – 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.

• Awesome, this is exactly what I was looking for, thx. – 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.

• In fact, for the torus there are more than 16,000 known forbidden minors! (See arxiv.org/abs/math/0411488 .) – José Figueroa-O'Farrill Nov 19 '10 at 18:07
• Which begs the question: why do 2 forbidden minors are enough in the plane? I mean, why so few? – Ori Gurel-Gurevich Nov 19 '10 at 18:49
• What's the approx number for genus 2? – 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.

• 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. – Tony Huynh May 18 '11 at 14:06