Linkless embedding

Short description: Embedding a graph in 3D space with no cycles interlinked

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. The complete graph K₆, the Petersen graph, and the other five graphs in the Petersen family do not have linkless embeddings. Every graph minor of a linklessly embeddable graph is again linklessly embeddable, as is every graph that can be reached from a linklessly embeddable graph by YΔ- and ΔY-transformations. The linklessly embeddable graphs have the Petersen family graphs as their forbidden minors, and include the planar graphs and apex graphs. They may be recognized, and a flat embedding may be constructed for them, in O(n²).

Definitions

Two linked curves forming a Hopf link.

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. Two disjoint closed curves that both lie on the same plane are unlinked, and more generally a pair of disjoint closed curves is said to be unlinked when there is a continuous deformation of space that moves them both onto the same plane, without either curve passing through the other or through itself. If there is no such continuous motion, the two curves are said to be linked. For example, the Hopf link is formed by two circles that each pass through the disk spanned by the other. It forms the simplest example of a pair of linked curves, but it is possible for curves to be linked in other more complicated ways. If two curves are not linked, then it is possible to find a topological disk in space, having the first curve as its boundary and disjoint from the second curve. Conversely if such a disk exists then the curves are necessarily unlinked.

The linking number of two closed curves in three-dimensional space is a topological invariant of the curves: it is a number, defined from the curves in any of several equivalent ways, that does not change if the curves are moved continuously without passing through each other. The version of the linking number used for defining linkless embeddings of graphs is found by projecting the embedding onto the plane and counting the number of crossings of the projected embedding in which the first curve passes over the second one, modulo 2. 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

The Petersen family.

As (Sachs 1983) 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 K₆, the Petersen graph, the graph formed by removing an edge from the complete bipartite graph K_4,4, and the complete tripartite graph K_3,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.

An apex graph. If the planar part of the graph is embedded on a flat plane in space, and the apex vertex is placed above the plane and connected to it by straight line segments, the resulting embedding is flat.

An apex graph, formed by adding a single vertex to a planar graph, also has a flat and linkless embedding: embed the planar part of the graph on a plane, place the apex above the plane, and draw the edges from the apex to its neighbors as line segments. Any closed curve within the plane bounds a disk below the plane that does not pass through any other graph feature, and any closed curve through the apex bounds a disk above the plane that does not pass through any other graph feature.

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

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

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

Related families of graphs

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 (Robertson Seymour) conjectured and (Lovász Schrijver) proved, the graphs with μ ≤ 4 are exactly the linklessly embeddable graphs.

Apex graphs

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. The YΔY reducible graphs are the graphs that can be reduced to a single vertex by YΔ- and ΔY-transformations, removal of isolated vertices and degree-one vertices, and compression of degree-two vertices; they are also minor-closed, and include all planar graphs. However, there exist linkless graphs that are not YΔY reducible, such as the apex graph formed by connecting an apex vertex to every degree-three vertex of a rhombic dodecahedron. 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.

Knotless graphs

Related to the concept of linkless embedding is the concept of knotless embedding, an embedding of a graph in such a way that none of its simple cycles form a nontrivial knot. The graphs that do not have knotless embeddings (that is, they are intrinsically knotted) include K₇ and K_3,3,1,1. 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.

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. (Flapan Naimi) 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 K₉ is not intrinsically triple linked, but K₁₀ 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.

History

The question of whether K₆ has a linkless or flat embedding was posed within the topology research community in the early 1970s by (Bothe 1973). Linkless embeddings were brought to the attention of the graph theory community by Horst Sachs (1983), 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 K₆) do not have such embeddings. As (Nešetřil Thomas) 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 (Robertson Seymour), 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.

(Sachs 1983) 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, and (Mader 1968) proved a matching upper bound on the more general class of K₆-minor-free graphs. (Nešetřil Thomas) 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 proof by (Robertson Seymour) of the case k = 6 of Hadwiger's conjecture is sufficient to settle Sachs' question: the linkless graphs can be colored with at most five colors, as any 6-chromatic graph contains a K₆ minor and is not linkless, and there exist linkless graphs such as K₅ that require five colors. 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) and (Motwani Raghunathan). Algorithmically, the problem of recognizing linkless and flat embeddable graphs was settled once the forbidden minor characterization was proven: an algorithm of (Robertson Seymour) can be used to test in polynomial time whether a given graph contains any of the seven forbidden minors. 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).

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?

See also

• Knots and graphs

References

• Böhme, Thomas (1990), "On spatial representations of graphs", in Bodendieck, Rainer, Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner, Mannheim: Bibliographisches Institut, Wissenschaftsverlag, pp. 151–167, ISBN 978-3-411-14301-6 . As cited by (Robertson Seymour).
• Bothe, H.-G. (1973), "Problem P855", Colloquium Mathematicum 28: 163, New Scottish Book, Problem 876, 20.5.1972 . As cited by (Sachs 1983).
• Bowlin, Garry; Foisy, Joel (2004), "Some new intrinsically 3-linked graphs", Journal of Knot Theory and its Ramifications 13 (8): 1021–1028, doi:10.1142/S0218216504003652, https://zenodo.org/record/894516/files/article.pdf .
• "Knots and links in spatial graphs", Journal of Graph Theory 7 (4): 445–453, 1983, doi:10.1002/jgt.3190070410 .
• "Nonconstructive tools for proving polynomial-time decidability", Journal of the ACM 35 (3): 727–739, 1988, doi:10.1145/44483.44491 .
• "Intrinsic linking and knotting of graphs in arbitrary 3–manifolds", Algebraic & Geometric Topology 6: 1025–1035, 2006, doi:10.2140/agt.2006.6.1025 .
• "Intrinsically triple linked complete graphs", Topology and its Applications 115 (2): 239–246, 2001, doi:10.1016/S0166-8641(00)00064-X, http://pages.pomona.edu/~elf04747/Research/I3L.pdf .
• "Intrinsically n-linked graphs", Journal of Knot Theory and Its Ramifications 10 (8): 1143–1154, 2001, doi:10.1142/S0218216501001360 .
• Fleming, Thomas; Diesl, Alexander (2005), "Intrinsically linked graphs and even linking number", Algebraic & Geometric Topology 5: 1419–1432, doi:10.2140/agt.2005.5.1419 .
• Foisy, Joel (2002), "Intrinsically knotted graphs", Journal of Graph Theory 39 (3): 178–187, doi:10.1002/jgt.10017 .
• Foisy, Joel (2003), "A newly recognized intrinsically knotted graph", Journal of Graph Theory 43 (3): 199–209, doi:10.1002/jgt.10114 .
• "The computational complexity of knot and link problems", Journal of the ACM 46 (2): 185–211, 1999, doi:10.1145/301970.301971 .
• van der Holst, Hein (2009), "A polynomial-time algorithm to find a linkless embedding of a graph", Journal of Combinatorial Theory, Series B 99 (2): 512–530, doi:10.1016/j.jctb.2008.10.002 .
• "Linkless and flat embeddings in 3-space and the unknot problem", Proc. ACM Symposium on Computational Geometry (SoCG '10), 2010, pp. 97–106, doi:10.1145/1810959.1810975 .
• "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs", Proceedings of the American Mathematical Society 126 (5): 1275–1285, 1998, doi:10.1090/S0002-9939-98-04244-0 .
• Mader, W. (1968), "Homomorphiesätze für Graphen", Mathematische Annalen 178 (2): 154–168, doi:10.1007/BF01350657 .
• "Constructive results from graph minors: linkless embeddings", Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS '88), 1988, pp. 398–409, doi:10.1109/SFCS.1988.21956 .
• Nešetřil, Jaroslav; Thomas, Robin (1985), "A note on spatial representation of graphs", Commentationes Mathematicae Universitatis Carolinae 26 (4): 655–659, archived from the original on 2011-07-18, https://web.archive.org/web/20110718171201/http://dspace.dml.cz/handle/10338.dmlcz/106404 .
• "Graph Minors. XIII. The disjoint paths problem", Journal of Combinatorial Theory, Series B 63 (1): 65–110, 1995, doi:10.1006/jctb.1995.1006 .
• "A survey of linkless embeddings", Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics, 147, American Mathematical Society, 1993a, pp. 125–136, http://people.math.gatech.edu/~thomas/PAP/linklsurvey.pdf .
• "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society 28 (1): 84–89, 1993b, doi:10.1090/S0273-0979-1993-00335-5 .
• "Sachs' linkless embedding conjecture", Journal of Combinatorial Theory, Series B 64 (2): 185–227, 1995, doi:10.1006/jctb.1995.1032 .
• "Hadwiger's conjecture for K₆-free graphs", Combinatorica 13 (3): 279–361, 1993c, doi:10.1007/BF01202354, http://people.math.gatech.edu/~thomas/PAP/hadwiger.pdf .
• Horowiecki, M.; Kennedy, J. W.; Sysło, M. M., eds. (1983), "On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem", Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, 1018, Springer-Verlag, pp. 230–241, doi:10.1007/BFb0071633 .
• Saran, Huzur (1989), Constructive Results in Graph Minors: Linkless Embeddings, Ph.D. thesis, University of California, Berkeley .
• Truemper, Klaus (1992), Matroid Decomposition, Academic Press, pp. 100–101, http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf .

Further reading

• Ramírez Alfonsín, J. L. (2005), "Knots and links in spatial graphs: a survey", Discrete Mathematics 302 (1–3): 225–242, doi:10.1016/j.disc.2004.07.035 .