Obstructions for planar graphs on surfaces of genus g - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T20:15:19Z http://mathoverflow.net/feeds/question/46655 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46655/obstructions-for-planar-graphs-on-surfaces-of-genus-g Obstructions for planar graphs on surfaces of genus g Dr Shello 2010-11-19T17:37:09Z 2011-05-17T21:58:19Z <p>Kurotowski'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.</p> <blockquote> <p>Is the list of obstructions to being able to embedded a graph with no edge-crossings on the surface of genus $g$ known to be finite for all $g$?</p> </blockquote> http://mathoverflow.net/questions/46655/obstructions-for-planar-graphs-on-surfaces-of-genus-g/46656#46656 Answer by Louigi Addario-Berry for Obstructions for planar graphs on surfaces of genus g Louigi Addario-Berry 2010-11-19T17:40:21Z 2010-11-19T18:23:55Z <p>Yes. <a href="http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="nofollow">Wagner's Conjecture/Robertson and Seymour's Theorem</a> 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. </p> <p>I haven't looked carefully at it but <a href="http://cornellmath.wordpress.com/2007/07/04/graph-minor-theory-part-3/" rel="nofollow">Jim Belk's introduction to graph minor theory</a> 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 <strike>hundreds</strike> thousands (at least, the precise number/collection is not known), and in general the number of forbidden minors grows exponentially with the genus. </p> http://mathoverflow.net/questions/46655/obstructions-for-planar-graphs-on-surfaces-of-genus-g/46666#46666 Answer by Tony Huynh for Obstructions for planar graphs on surfaces of genus g Tony Huynh 2010-11-19T18:37:19Z 2010-11-19T21:10:30Z <p>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:</p> <ol> <li><p><strong>The Grid Theorem</strong>. 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.</p></li> <li><p><strong>Graphs of bounded tree-width are well-quasi-ordered.</strong> For any $k$, the class of graphs of tree-width at most $k$ is well-quasi-ordered.</p></li> <li><p><strong>Forbidden minors for surfaces do not contain arbitrarily large grid minors.</strong> 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. </p></li> </ol> <p>All three of these facts now have very compact proofs. In fact, proofs for all three are included in the third and fourth editions of Diestel's <em>Graph Theory.</em> See <a href="http://diestel-graph-theory.com/" rel="nofollow">here</a> to peruse the book online. </p> http://mathoverflow.net/questions/46655/obstructions-for-planar-graphs-on-surfaces-of-genus-g/65277#65277 Answer by Paul for Obstructions for planar graphs on surfaces of genus g Paul 2011-05-17T21:58:19Z 2011-05-17T21:58:19Z <p>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: <a href="http://www.emba.uvm.edu/~archdeac/" rel="nofollow">http://www.emba.uvm.edu/~archdeac/</a> 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.</p>