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.[1] Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.
Flat embeddings are automatically linkless, but not vice versa.[2] The complete graphK6, the Petersen graph, and the other five graphs in the Petersen family do not have linkless embeddings.[1] Every graph minor of a linklessly embeddable graph is again linklessly embeddable,[3] as is every graph that can be reached from a linklessly embeddable graph by YΔ- and ΔY-transformations.[2] The linklessly embeddable graphs have the Petersen family graphs as their forbidden minors,[4] and include the planar graphs and apex graphs.[2] They may be recognized, and a flat embedding may be constructed for them, in O(n2).[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. 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 topologicalinvariant 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.[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.[6]
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.[7] 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.[8]
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 graphK6, the Petersen graph, the graph formed by removing an edge from the complete bipartite graphK4,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.[2]
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.[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.
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.[3]
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.[5] Testing unknottedness (and therefore, also, testing linklessness of an embedding) is known to be in NP but is not known to be NP-complete.[9]
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 & Thomas (1993a) conjectured and Lovász & Schrijver (1998) 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.[2] 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.[10] 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.[2]
Knotless graphs
A closed curve forming a trefoil, the simplest nontrivial knot.
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 K7 and K3,3,1,1.[11] 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.[12]
One may also define graph families by the presence or absence of more complex knots and links in their embeddings,[13] or by linkless embedding in three-dimensional manifolds other than Euclidean space.[14]Flapan, Naimi & Pommersheim (2001) 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.[15] 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.[16]
History
The question of whether K6 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 HorstSachs(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 K6) do not have such embeddings. As Nešetřil & Thomas (1985) 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 & Thomas (1995),[17] 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: maximalapex graphs with n>4 have exactly this many edges,[1] and Mader (1968) proved a matching upper bound on the more general class of K6-minor-free graphs. 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 proof by Robertson, Seymour & Thomas (1993c) 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 K6 minor and is not linkless, and there exist linkless graphs such as K5 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 (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?
↑ The application of the Robertson–Seymour algorithm to this problem was noted by Fellows & Langston (1988).
Related Research Articles
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
In mathematics, a knot is an embedding of the circle into three-dimensional Euclidean space, R3. Often two knots are considered equivalent if they are ambient isotopic, that is, if there exists a continuous deformation of R3 which takes one knot to the other.
In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.
In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G. Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.
Colin de Verdière's invariant is a graph parameter for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 nor K3,3. This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.
In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner, Fáry, and Sherman K. Stein.
In topological graph theory, an embedding of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs are associated with edges in such a way that:
In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph.
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.
In graph theory, a planar cover of a finite graph G is a finite covering graph of G that is itself a planar graph. Every graph that can be embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers.
In graph theory, ΔY- and YΔ-transformations are a pair of operations on graphs. A ΔY-transformation replaces a triangle by a vertex of degree three; and conversely, a YΔ-transformation replaces a vertex of degree three by a triangle. The names for the operations derive from the shapes of the involved subgraphs, which look respectively like the letter Y and the Greek capital letter Δ.
References
Böhme, Thomas (1990), "On spatial representations of graphs", in Bodendieck, Rainer (ed.), Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner, Mannheim: Bibliographisches Institut, Wissenschaftsverlag, pp.151–167, ISBN978-3-411-14301-6 . As cited by Robertson, Seymour & Thomas (1993a).
Bothe, H.-G. (1973), "Problem P855", Colloquium Mathematicum, 28: 163, New Scottish Book, Problem 876, 20.5.1972. As cited by Sachs (1983).
Sachs, Horst (1983), "On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem", in Horowiecki, M.; Kennedy, J. W.; Sysło, M. M. (eds.), Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol.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.
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 .
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
