| Affiliation: | 1.National Institute of Informatics,Chiyoda-ku, Tokyo,Japan;2.Department of Computer Science,University of Oxford,Oxford,UK;3.Department of Mathematics,Simon Fraser University,Burnaby,Canada |
| Abstract: | We consider piecewise linear embeddings of graphs in 3-space ℝ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 ℝ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Δ 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 embedding is linkless, but the converse is not true. We consider the following algorithmic problem associated with embeddings in ℝ3: |
