Linkless and flat embeddings in 3-space and the unknot problem
Ken‐ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar · 2010
We consider piecewise linear embeddings of graphs in 3-space ℜ3. Such an embbeding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas [47] showed that a graph has a linkless embedding in ℜ3 if, and only if, it does not contain as a minor any of seven graphs in Petersen's family (graphs obtained from K6 by a series of YΔ and ΔY operations). They also showed that a graph is linklessly embeddable in ℜ3 if, and only if, it admits a flat embedding into ℜ3, i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D ⊆ ℜ3 with D ∩ G = ∂D = C. Clearly, every flat embeddings is linkless, but the converse is not true. We first consider the following algorithmic problem associated with embeddings in ℜ3: