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
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.
K2-Think
The Robertson-Seymour Graph Minor Theorem states that any infinite sequence of graphs contains a pair where one is a minor of the other, implying that the set of all graphs is well-quasi-ordered by the minor relation. When considering planar graphs with a fixed embedding and requiring the minor operation to respect this embedding, the question arises whether this well-quasi-ordering still holds.
...
GPT-5
Yes. If you regard a plane graph as a graph together with a fixed combinatorial embedding (the cyclic order of edges around each vertex, equivalently an embedding on the sphere with a distinguished outer face), then the class of finite plane graphs is well–quasi–ordered by the minor relation taken in the plane (i.e., delete and contract edges in the given embedding, using the induced embedding on ...
o4 mini
Yes – in fact one can show exactly as in Kruskal’s theorem for trees that the set of all plane‐embedded graphs (often called “maps” on the sphere) is well‐quasi‐ordered by the operation of deleting or contracting edges in such a way that the given embedding is carried along. Equivalently:
Theorem. Let (G₁,π₁),(G₂,π₂),… be an infinite sequence of finite planar graphs each equipped with one...
Gemini 2.5 Pro
Excellent question. This gets to the heart of how the abstract, combinatorial nature of graph minors interacts with the geometric constraints of an embedding.
The short answer is yes, the Robertson-Seymour theorem does hold for planar graphs with an embedding-respecting minor operation. The set of finite plane graphs is a well-quasi-order under the planar minor relation.
However, as you ...
o3
No.
If the embedding has to be respected, plane graphs are not well-quasi-ordered by the minor relation: there is an infinite family of pairwise incomparable plane graphs. One convenient way to see this is to encode permutations in very small plane graphs.
- Encoding a permutation in a plane graph
For a permutation π of {1,…,n} build t...
DeepSeek R1
First, I recall that the Robertson-Seymour theorem states that graphs are well-quasi-ordered under minors, meaning there are no infinite antichains. The user mentions that this gene...
Claude Opus 4
This is an excellent question about the relationship between graph minor theory and planar embeddings.
The answer is no - the Robertson-Seymour theorem does not hold when we require minor operations to respect planar embeddings. In fact, there exist infinite antichains of plane graphs (planar graphs with fixed embeddings) under the topological minor relation.
Here's why:
Key Distinction
...
Claude 3.7 Sonnet
Planar Minor Graphs and Embedding-Respecting Minors
This is a nuanced question about extending the Robertson-Seymour theorem to the context of planar embedded graphs.
Background
The Robertson-Seymour theorem (Graph Minor Theorem) states that in any infinite family of finite graphs, there must exist two graphs such that one is a minor of the other. This powerful result was indeed a generali...
o3 Pro
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.
- What is meant by “respecting the embedding”.
• We work with plane ( = embedded planar) graphs.
• A minor operation is allowed to
– de...
You need to be logged in to submit an answer