Linkless Embedding - Characterization and Recognition

Characterization and Recognition

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. 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.

The set of forbidden minors for the linklessly embeddable graphs was identified by 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 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. 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 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. Testing unknottedness (and therefore, also, testing linklessness of an embedding) is known to be in NP but is not known to be NP-complete.