Title:
Linkless Embeddings in 3-space
Linkless Embeddings in 3-space
Files
Author(s)
Kreutzer, Stephan
Advisor(s)
Editor(s)
Collections
Supplementary to
Permanent Link
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.
Sponsor
NSF, NSA, ONR, IMA, Colleges of Sciences, Computing and Engineering
Date Issued
2012-05
Extent
Resource Type
Text
Resource Subtype
Proceedings