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.

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, *rooted ordered* 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.

Here comes the question: is Robertson-Seymour theorem true for planar graphs, when we add the condition that the minor operation respects the embedding? (*i.e.* we not only ask $G_i$ to be a minor of $G_j$ as an abstract graph, but also as an embedded graph.)

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.

i.e.that corresponds to the given embedding of $G_m$? – Pierre Dehornoy Mar 28 '12 at 23:46