## Linkless Embeddings in 3-space

##### Abstract

We consider piecewise linear embeddings of graphs in the 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 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. In this talk we present an algorithm running in time n^2 which, given a graph G as input either determines that G contains a graph of the Petersen family as minor, and hence is not linklessly embeddable, or computes a flat embedding of G. We also briefly discuss recent extension of this algorithm running in linear time.