Well-quasi-order of plane minors and an application to link diagrams

Abstract

A plane graph $H$ is a {\em plane minor} of a plane graph $G$ if there is a sequence of vertex and edge deletions, and edge contractions performed on the plane, that takes $G$ to $H$. Motivated by knot theory problems, it has been asked if the plane minor relation is a well-quasi-order. We settle this in the affirmative. We also prove an additional application to knot theory. If $L$ is a link and $D$ is a link diagram, write $D⇝L$ if there is a sequence of crossing exchanges and smoothings that takes $D$ to a diagram of $L$. We show that, for each fixed link $L$, there is a polynomial-time algorithm that takes as input a link diagram $D$ and answers whether or not $D⇝L$.

arXiv commentThe proof of Theorem 1.1 is incorrect. The problem is that good digraphs, which are introduced at the beginning of Section 2, are embedded objects, whereas the immersion order used in the proofs of Facts 2.2 and 2.3 refers to abstract digraphs. Thus the proofs of Facts 2.2 and 2.3 are incorrect, and these are essential ingredients in the proof of Theorem 1.1

References in corpus (3)

• Sub-chord diagrams of knot projections
• Minor theory for surfaces and divides of maximal signature
• Strong and weak (1, 2) homotopies on knot projections and new invariants