Linkless embedding

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

Flat embeddings are automatically linkless, but not vice versa. and include the planar graphs and apex graphs. The projection must be "regular", meaning that no two vertices project to the same point, no vertex projects to the interior of an edge, and at every point of the projection where the projections of two edges intersect, they cross transversally; with this restriction, any two projections lead to the same linking number.

The linking number of the unlink is zero, and therefore, if a pair of curves has nonzero linking number, the two curves must be linked. However, there are examples of curves that are linked but that have zero linking number, such as the Whitehead link.

An embedding of a graph into three-dimensional space consists of a mapping from the vertices of the graph to points in space, and from the edges of the graph to curves in space, such that each endpoint of each edge is mapped to an endpoint of the corresponding curve, and such that the curves for two different edges do not intersect except at a common endpoint of the edges.

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. One may compute the linking number of each disjoint pair of curves formed in this way; if all pairs of cycles have zero linking number, the embedding is said to be linkless.

In some cases, a graph may be embedded in space in such a way that, for each cycle in the graph, one can find a disk bounded by that cycle that does not cross any other feature of the graph. In this case, the cycle must be unlinked from all the other cycles disjoint from it in the graph. The embedding is said to be flat if every cycle bounds a disk in this way. A flat embedding is necessarily linkless, but there may exist linkless embeddings that are not flat: for instance, if G is a graph formed by two disjoint cycles, and it is embedded to form the Whitehead link, then the embedding is linkless but not flat.

A graph is said to be intrinsically linked if, no matter how it is embedded, the embedding is always linked. Although linkless and flat embeddings are not the same, the graphs that have linkless embeddings are the same as the graphs that have flat embeddings.

Examples and counterexamples

thumb|The [[Petersen family.]]

As showed, each of the seven graphs of the Petersen family is intrinsically linked: no matter how each of these graphs is embedded in space, they have two cycles that are linked to each other. These graphs include the complete graph K6, the Petersen graph, the graph formed by removing an edge from the complete bipartite graph K4,4, and the complete tripartite graph K3,3,1.

Every planar graph has a flat and linkless embedding: simply embed the graph into a plane and embed the plane into space. If a graph is planar, this is the only way to embed it flatly and linklessly into space: every flat embedding can be continuously deformed to lie on a flat plane. And conversely, every nonplanar linkless graph has multiple linkless embeddings.

The set of forbidden minors for the linklessly embeddable graphs was identified by : 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 .

The forbidden minor characterization of linkless graphs leads to a polynomial time algorithm for their recognition, but not for actually constructing an embedding. 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 . 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.

Graphs with small Colin de Verdière invariant

The Colin de Verdière graph invariant is an integer defined for any graph using algebraic graph theory. The graphs with Colin de Verdière graph invariant at most μ, for any fixed constant μ, form a minor-closed family, and the first few of these are well-known: the graphs with μ ≤ 1 are the linear forests (disjoint unions of paths), the graphs with μ ≤ 2 are the outerplanar graphs, and the graphs with μ ≤ 3 are the planar graphs. As conjectured and proved, the graphs with μ ≤ 4 are exactly the linklessly embeddable graphs.

Apex graphs

thumb|A linkless apex graph that is not YΔY reducible.

The planar graphs and the apex graphs are linklessly embeddable, as are the graphs obtained by YΔ- and ΔY-transformations from these graphs. There also exist linkless graphs that cannot be transformed into an apex graph by YΔ- and ΔY-transformation, removal of isolated vertices and degree-one vertices, and compression of degree-two vertices: for instance, the ten-vertex crown graph has a linkless embedding, but cannot be transformed into an apex graph in this way. However, there also exist minimal forbidden minors for knotless embedding that are not formed (as these two graphs are) by adding one vertex to an intrinsically linked graph, but the list of these is unknown.

One may also define graph families by the presence or absence of more complex knots and links in their embeddings, or by linkless embedding in three-dimensional manifolds other than Euclidean space. define a graph embedding to be triple linked if there are three cycles no one of which can be separated from the other two; they show that K9 is not intrinsically triple linked, but K10 is. More generally, one can define an n-linked embedding for any n to be an embedding that contains an n-component link that cannot be separated by a topological sphere into two separated parts; minor-minimal graphs that are intrinsically n-linked are known for all n.

Directed graphs

A directed graph is said to be intrinsically linked if it contains a nontrivial link consisting of a pair of consistently oriented directed cycles in every spatial embedding. In contrast to undirected graphs, edge contraction and ∆−Y operations do not necessarily preserve linkless embeddability.

History

The question of whether K6 has a linkless or flat embedding was posed within the topology research community in the early 1970s by . Linkless embeddings were brought to the attention of the graph theory community by , who posed several related problems including the problem of finding a forbidden graph characterization of the graphs with linkless and flat embeddings; Sachs showed that the seven graphs of the Petersen family (including K6) do not have such embeddings. As observed, linklessly embeddable graphs are closed under graph minors, from which it follows by the Robertson–Seymour theorem that a forbidden graph characterization exists. The proof of the existence of a finite set of obstruction graphs does not lead to an explicit description of this set of forbidden minors, but it follows from Sachs' results that the seven graphs of the Petersen family belong to the set. These problems were finally settled by , who showed that the seven graphs of the Petersen family are the only minimal forbidden minors for these graphs. Therefore, linklessly embeddable graphs and flat embeddable graphs are both the same set of graphs, and are both the same as the graphs that have no Petersen family minor.

also asked for bounds on the number of edges and the chromatic number of linkless embeddable graphs. The number of edges in an n-vertex linkless graph is at most 4n − 10: maximal apex graphs with n > 4 have exactly this many edges, This method does not construct linkless or flat embeddings when they exist, but an algorithm that does construct an embedding was developed by , and a more efficient linear time algorithm was found by .

A final question of 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?

Notes

References

. As cited by .
. As cited by .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.