Linkless embedding
[5] When the circle is mapped to three-dimensional Euclidean space by an injective function (a continuous function that does not map two different points of the circle to the same point of space), its image is a closed curve.
For example, the Hopf link is formed by two circles that each pass through the disk spanned by the other.
Any finite graph has a finite (though perhaps exponential) number of distinct simple cycles, and if the graph is embedded into three-dimensional space then each of these cycles forms a simple closed curve.
[2] If a graph has a linkless or flat embedding, then modifying the graph by subdividing or unsubdividing its edges, adding or removing multiple edges between the same pair of points, and performing YΔ- and ΔY-transformations that replace a degree-three vertex by a triangle connecting its three neighbors or the reverse all preserve flatness and linklessness.
[2] In particular, in a cubic planar graph (one in which all vertices have exactly three neighbors, such as the cube) it is possible to make duplicates of any independent set of vertices by performing a YΔ-transformation, adding multiple copies of the resulting triangle edges, and then performing the reverse ΔY-transformations.
If a graph G has a linkless or flat embedding, then every minor of G (a graph formed by contraction of edges and deletion of edges and vertices) also has a linkless or flat embedding.
However, Sachs was unable to prove that these were the only minimal linked graphs, and this was finally accomplished by Robertson, Seymour & Thomas (1995).
The forbidden minor characterization of linkless graphs leads to a polynomial time algorithm for their recognition, but not for actually constructing an embedding.
The problem of efficiently testing whether a given embedding is flat or linkless was posed by Robertson, Seymour & Thomas (1993a).
Nešetřil & Thomas (1985) observed that Sachs' question about the chromatic number would be resolved by a proof of Hadwiger's conjecture that any k-chromatic graph has as a minor a k-vertex complete graph.
The snark theorem implies that every cubic linklessly embeddable graph is 3-edge-colorable.
Linkless embeddings started being studied within the algorithms research community in the late 1980s through the works of Fellows & Langston (1988) and Motwani, Raghunathan & Saran (1988).
Algorithmically, the problem of recognizing linkless and flat embeddable graphs was settled once the forbidden minor characterization was proven: an algorithm of Robertson & Seymour (1995) can be used to test in polynomial time whether a given graph contains any of the seven forbidden minors.
[18] This method does not construct linkless or flat embeddings when they exist, but an algorithm that does construct an embedding was developed by van der Holst (2009), and a more efficient linear time algorithm was found by Kawarabayashi, Kreutzer & Mohar (2010).
A final question of Sachs (1983) on the possibility of an analogue of Fáry's theorem for linkless graphs appears not to have been answered: when does the existence of a linkless or flat embedding with curved or piecewise linear edges imply the existence of a linkless or flat embedding in which the edges are straight line segments?
