Editing Linkless embedding (section)

==Characterization and recognition==
If a graph ''G'' has a linkless or flat embedding, then every [[minor (graph theory)|minor]] of ''G'' (a graph formed by contraction of edges and deletion of edges and vertices) also has a linkless or flat embedding. Deletions cannot destroy the flatness of an embedding, and a contraction can be performed by leaving one endpoint of the contracted edge in place and rerouting all the edges incident to the other endpoint along the path of the contracted edge. Therefore, by the [[Robertson–Seymour theorem]], the linklessly embeddable graphs have a [[forbidden graph characterization]] as the graphs that do not contain any of a finite set of minors.<ref name="nt85">{{harvtxt|Nešetřil|Thomas|1985}}</ref>

The set of forbidden minors for the linklessly embeddable graphs was identified by {{harvtxt|Sachs|1983}}: the seven graphs of the [[Petersen family]] are all minor-minimal intrinsically linked graphs. However, Sachs was unable to prove that these were the only minimal linked graphs, and this was finally accomplished by {{harvtxt|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. {{harvtxt|Kawarabayashi|Kreutzer|Mohar|2010}} described a linear time algorithm that tests whether a graph is linklessly embeddable and, if so, constructs a flat embedding of the graph. Their algorithm finds large planar subgraphs within the given graph such that, if a linkless embedding exists, it has to respect the planar embedding of the subgraph. By repeatedly simplifying the graph whenever such a subgraph is found, they reduce the problem to one in which the remaining graph has bounded [[treewidth]], at which point it can be solved by [[dynamic programming]].

The problem of efficiently testing whether a given embedding is flat or linkless was posed by {{harvtxt|Robertson|Seymour|Thomas|1993a}}. It remains unsolved, and is equivalent in complexity to [[unknotting problem]], the problem of testing whether a single curve in space is unknotted.<ref name="kkm10">{{harvtxt|Kawarabayashi|Kreutzer|Mohar|2010}}</ref> Testing unknottedness (and therefore, also, testing linklessness of an embedding) is known to be in [[NP (complexity)|NP]] but is not known to be [[NP-complete]].<ref>{{harvtxt|Hass|Lagarias|Pippenger|1999}}.</ref>