2019/05/06 by Carolina Medina, Medina, Carolina, Bojan Mohar +3 · 1 citation
Computer Science · Mathematics · #05C10 #05C83 #57M15 #57M25 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric Topology (math.GT) #Geometric and Algebraic Topology
paper · pdf · doi:10.48550/arxiv.1905.01830
openalex publication_date 2019/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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\leadsto 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\leadsto L.