A plane graph is a finite simple graph with a fixed embedding into the two-sphere. The embedding induces an embedding on a minors of a plane graph (i.e. a graph obtained by successive removal of vertices, removal of edges, and contraction of edges). In other words, we may consider minors of plane graphs to be plane graphs themselves. These minors are called surface minors.
The surface-minor relation is an ordering on plane graphs, which is finer than the minor relation: a plane graph may be a minor of another plane graph, without being a surface minor (indeed, if a graph has several non-isomorphic embeddings into the two-sphere, then these are examples of that behavior).
The question is:
Is the surface-minor ordering of plane graphs a well-quasi-ordering? That is to say, is there among any infinite collection of plane graphs a pair of two plane graphs, one of which is a surface minor of the other?
This seems a very natural question to me, yet I couldn't find an answer in the literature. One would assume that this question must be answered in one of Robertson and Seymour's papers, since both the notion of well-quasi-orderings and the notion of surface minors are pretty central in them.
If one restricts oneself to plane trees, the answer is positive: this is a version of Kruskal's Tree Theorem.
The answer is also positive if one restricts oneself to 3-connected plane graphs, since Whitney's Theorem says that they have a unique embedding, and so the surface-minor and the minor relation coincide.
Of course, one can ask this question not only about the two-sphere, but about any other fixed (not necessarily orientable) closed surface.
Please note this question is not a direct corollary of the Robertson-Seymour theorem that the minor ordering on finite graphs is a well-quasi-ordering; and it does not have a direct relation to Kuratowski's Theorem, which gives the two forbidden minors for planar graphs (not to be confused with the plane graphs this question is about).
