WELL-QUASI-ORDER OF PLANE MINORS AND AN APPLICATION TO LINK DIAGRAMS

NEW

Problem: Interpreting the question as the variable plane-minor decision problem:

Input: finite plane graphs $H,G$.
Question: is $H\preceq_{\mathbb R^2}G$, i.e. can $H$ be obtained from $G$, up to combinatorial equivalence of plane embeddings, by plane vertex deletions, edge deletions, and edge contractions?

This matches the paper’s plane-minor notation and its fixed-pattern algorithm; the symbol in the prompt is ambiguous, but the supplied context points to the plane-minor relation.

Result: The decision problem is NP-complete, even when $H$ is a cycle and $G$ is a simple connected plane graph.

Membership in NP is immediate: a certificate is a sequence of deletions/contractions, of length at most $|V(G)|+|E(G)|$, plus a final combinatorial isomorphism to $H$; it can be checked in polynomial time.

For NP-hardness, reduce from Planar Hamiltonian Cycle. Given a simple planar graph $G$ with $n\ge3$ vertices, compute a plane embedding and let $H=C_n$ with its standard plane embedding.

If $G$ has a Hamiltonian cycle, deleting all non-cycle edges leaves a plane $n$-cycle, so $C_n\preceq_{\mathbb R^2}G$.

Conversely, if $C_n\preceq_{\mathbb R^2}G$, then since $|V(C_n)|=|V(G)|=n$, no vertex deletion or edge contraction can occur in a successful minor sequence, because both strictly decrease the number of vertices. Hence only edge deletions occur, and $G$ contains a spanning subgraph combinatorially equal to $C_n$, i.e. a Hamiltonian cycle.

Thus $G$ is Hamiltonian iff $C_n\preceq_{\mathbb R^2}G$, giving a polynomial many-one reduction. Therefore the variable plane-minor relation is NP-complete.

Citation: Uses NP-completeness of Planar Hamiltonian Cycle: Garey, Johnson, and Tarjan, “The planar Hamiltonian circuit problem is NP-complete,” SIAM J. Comput. 5 (1976), 704–714.