Linkless and Flat Embeddings in 3-Space
We consider piecewise linear embeddings of graphs in 3-space R-3. Such an embedding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas (J. Comb. Theory, Ser. B 64:185-227, 1995) showed that a graph has a linkless embedding in R-3 if and only if it does not contain as a minor any of seven graphs in Petersen's family (graphs obtained from K-6 by a series of Y Delta and Delta Y operations). They also showed that a graph is linklessly embeddable in R-3 if and only if it admits a flat embedding into R-3, i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D subset of R-3 with D boolean AND G = partial derivative D = C. Clearly, every flat embedding is linkless, but the converse is not true. We consider the following algorithmic problem associated with embeddings in R-3: FLAT EMBEDDING: For a given graph G, either detect one of Petersen's family graphs as a minor in G, or return a flat (and hence linkless) embedding of G in R-3. The first outcome is a certificate that G has no linkless and no flat embeddings. Our main result is to give an O(n(2)) algorithm for this problem. While there is a known polynomial-time algorithm for constructing linkless embeddings (van der Holst in J. Comb. Theory, Ser. B 99:512-530, 2009), this is the first polynomial-time algorithm for constructing flat embeddings in 3-space. This settles a problem proposed by Lovasz (www.cs.elte.hu/similar to lovasz/klee.ppt, 2000).
flat embedding knot linkless embedding unknot