most recent 30 from http://mathoverflow.net 2013-06-19T22:53:35Z http://mathoverflow.net/feeds/question/92421 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92421/planar-minor-graphs Pierre Dehornoy 2012-03-27T23:28:06Z 2012-03-28T11:24:22Z

<p>The theorem of Robertson-Seymour about graph minors says that there exists no infinite family of graphs such that none of them is a minor of another one.</p> <p>Apparently, it came as a generalization of the Kruskal's theorem that states that there exists no infinite family of rooted ordered trees such that none is a minor of another one. Here, <em>rooted ordered</em> means that the tree has a root, and that the edges escaping from a vertex are ordered. In other words, the trees are assumed to be embedded in the plane, and the minor operation has to respect this embedding.</p> <p>Here comes the question: is Robertson-Seymour theorem true for planar graphs, when we add the condition that the minor operation respects the embedding? (<em>i.e.</em> we not only ask $G_i$ to be a minor of $G_j$ as an abstract graph, but also as an embedded graph.)</p> <p>It is not clear to me that this should be a direct corollary of the original theorem, because of the amount of possible embeddings into the plane for a given planar graph.</p>