Short answer. Nobody knows. Whether the set of all finite plane-graphs is well-quasi-ordered under the minor relation that has to respect the fixed embedding (usually called map–minors or embedded minors) is an open problem.

Explanation.

1. What is meant by “respecting the embedding”.
   • We work with plane ( = embedded planar) graphs.
   • A minor operation is allowed to
   – delete a vertex or an edge,
   – contract an edge,
   but the contraction has to be performed in the drawing itself, so that the cyclic orders of the remaining half–edges are the ones induced by the original drawing.
   In the language of topological graph theory we are taking minors in the category of “maps”.

2. Relation with the Robertson–Seymour theorem.
   The usual Graph–Minor Theorem shows that the class of all finite graphs (regarded abstractly) is well-quasi-ordered. Unfortunately this does not settle the question for embedded graphs, because the same abstract graph may possess many different embeddings and the theorem gives no control over them.

3. Partial results that are known.
   • Trees. Kruskal’s theorem (1960) already implies that rooted ordered trees – i.e. plane trees – are wqo by embedded minors.
   • Bounded tree-width. Courcelle, and independently Adler–Grohe–Kreutzer, proved that for every fixed k the class of plane graphs of tree-width ≤ k is wqo by embedded minors.
   • Outerplanar maps, series–parallel maps, etc. are also known to be wqo (again by reductions to the tree case).
   • On the other hand no one has been able to construct an infinite antichain of embedded planar graphs; the existence of such an antichain would settle the problem in the negative.

4. How the problem appears in the literature.
   The question is usually referred to as “the map-minor conjecture” or “the embedded minor conjecture”. It is attributed to Robertson and Seymour (see, e.g., Graph Minors X, §7) and is regarded as one of the major open problems that remain after the graph-minor series.

5. Why the known techniques do not decide it.
   In the labelled-graph extension of the Graph-Minor Theorem the set of labels has to be a fixed wqo. To encode a cyclic ordering at a vertex of unbounded degree one would need an unbounded amount of information, and the obvious encodings lead to label sets that are not wqo (because different permutations form an infinite antichain). Hence a new idea seems to be required.

Thus, at present we only have partial positive results and no counter- example, and the general well-quasi-ordering of plane graphs by embedding-respecting minors remains open.