Linkless embedding
Encyclopedia
In topological graph theory
, a mathematical discipline, a linkless embedding of an undirected graph is an embedding
of the graph into Euclidean space
in such a way that no two cycles of the graph have nonzero linking number
. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk
that is not crossed by any other feature of 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 graph
s.
Flat embeddings are automatically linkless, but not vice versa. The complete graph
K6, the Petersen graph
, and the other five graphs in the Petersen family
do not have linkless embeddings. The linklessly embeddable graphs are closed under graph minors and Y-Δ transforms, have the Petersen family graphs as their forbidden minors, and include the planar graphs and apex graph
s. They may be recognized, and a flat embedding may be constructed for them, in linear time.
are said to be unlink
ed if there is a continuous motion of the curves which transforms them into disjoint coplanar circles without one curve passing through the other or through itself. If there is no such continuous motion, they are said to be linked
. The Hopf link, formed by two circles that each pass through the disk spanned by the other, 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 disk in space, bounded by the first curve and disjoint from the second curve, and 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 unknot 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 turn out to be the same as the graphs that have flat embeddings.
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 linklessly into space: every linkless embedding can be continuously deformed to lie on a flat plane. And conversely, every nonplanar linkless graph has multiple linkless embeddings.
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-Δ transforms 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 Y-Δ transforms, adding multiple copies of the resulting triangle edges, and then performing the reverse Δ-Y transforms.
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 : 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
.
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 graph
s, and the graphs with μ ≤ 3 are the planar graph
s. As conjectured and proved, the graphs with μ ≤ 4 are exactly the linklessly embeddable graphs.
The planar graphs and the apex graph
s are linklessly embeddable, as are the graphs obtained by Y-Δ transforms from these graphs. The YΔY reducible graphs are the graphs that can be reduced to a single vertex by Y-Δ transforms, 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-Δ transforms, 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.
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 include K7 and K3,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. 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.
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 graph
s with n > 4 have exactly this many edges, and proved a matching upper bound on the more general class of K6-minor-free graphs. 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 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 algorithm
s research community in the late 1980s through the works of and . Algorithmically, the problem of recognizing linkless and flat embeddable graphs was settled once the forbidden minor characterization was proven: an algorithm of 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 , 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 segment
s?
Topological graph theory
In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs....
, a mathematical discipline, a linkless embedding of an undirected graph is an embedding
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
of the graph into Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
in such a way that no two cycles of the graph have nonzero linking number
Linking number
In mathematics, the linking number is a numerical invariant that describes the linking of two closed curves in three-dimensional space. Intuitively, the linking number represents the number of times that each curve winds around the other...
. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk
Disk (mathematics)
In geometry, a disk is the region in a plane bounded by a circle.A disk is said to be closed or open according to whether or not it contains the circle that constitutes its boundary...
that is not crossed by any other feature of 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 graph
Planar graph
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...
s.
Flat embeddings are automatically linkless, but not vice versa. The complete graph
Complete graph
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.-Properties:...
K6, the Petersen graph
Petersen graph
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 for Julius Petersen, who in 1898 constructed it...
, and the other five graphs in the Petersen family
Petersen family
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....
do not have linkless embeddings. The linklessly embeddable graphs are closed under graph minors and Y-Δ transforms, have the Petersen family graphs as their forbidden minors, and include the planar graphs and apex graph
Apex 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. We say an apex, not the apex because an apex graph may have more than one apex...
s. They may be recognized, and a flat embedding may be constructed for them, in linear time.
Definitions
Two disjoint curves in Euclidean spaceEuclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
are said to be unlink
Unlink
In the mathematical field of knot theory, the unlink is a link that is equivalent to finitely many disjoint circles in the plane.- Properties :...
ed if there is a continuous motion of the curves which transforms them into disjoint coplanar circles without one curve passing through the other or through itself. If there is no such continuous motion, they are said to be linked
Link (knot theory)
In mathematics, a link is a collection of knots which do not intersect, but which may be linked together. A knot can be described as a link with one component. Links and knots are studied in a branch of mathematics called knot theory...
. The Hopf link, formed by two circles that each pass through the disk spanned by the other, 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 disk in space, bounded by the first curve and disjoint from the second curve, and conversely if such a disk exists then the curves are necessarily unlinked.
The linking number
Linking number
In mathematics, the linking number is a numerical invariant that describes the linking of two closed curves in three-dimensional space. Intuitively, the linking number represents the number of times that each curve winds around the other...
of two closed curves in three-dimensional space is a topological
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
invariant
Invariant (mathematics)
In mathematics, an invariant is a property of a class of mathematical objects that remains unchanged when transformations of a certain type are applied to the objects. The particular class of objects and type of transformations are usually indicated by the context in which the term is used...
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
Crossing number (graph theory)
In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
of the projected embedding in which the first curve passes over the second one, modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
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 unknot 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
Whitehead link
In knot theory, the Whitehead link, discovered by J.H.C. Whitehead, is one of the most basic links.J.H.C. Whitehead spent much of the 1930s looking for a proof of the Poincaré conjecture...
.
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
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
, 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 turn out to be the same as the graphs that have flat embeddings.
Examples and counterexamples
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 graphComplete graph
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.-Properties:...
K6, the Petersen graph
Petersen graph
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 for Julius Petersen, who in 1898 constructed it...
, the graph formed by removing an edge from the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K4,4, and the complete tripartite graph K3,3,1.
Every planar graph
Planar graph
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...
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 linklessly into space: every linkless embedding can be continuously deformed to lie on a flat plane. And conversely, every nonplanar linkless graph has multiple linkless embeddings.
An apex graph
Apex 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. We say an apex, not the apex because an apex graph may have more than one apex...
, 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-Δ transforms 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
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
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
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
of vertices by performing Y-Δ transforms, adding multiple copies of the resulting triangle edges, and then performing the reverse Δ-Y transforms.
Characterization and recognition
If a graph G has a linkless or flat embedding, then every minorMinor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
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
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
, 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 : the seven graphs of the Petersen family
Petersen family
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....
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
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
.
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
Unknotting problem
In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms...
, 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
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
but is not known to be NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
.
Related families of graphs
The Colin de Verdière graph invariantColin de Verdière graph invariant
Colin de Verdière's invariant is a graph parameter \mu 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.-Definition:...
is an integer defined for any graph using algebraic graph theory
Algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...
. 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 graph
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
s, and the graphs with μ ≤ 3 are the planar graph
Planar graph
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...
s. As conjectured and proved, the graphs with μ ≤ 4 are exactly the linklessly embeddable graphs.
The planar graphs and the apex graph
Apex 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. We say an apex, not the apex because an apex graph may have more than one apex...
s are linklessly embeddable, as are the graphs obtained by Y-Δ transforms from these graphs. The YΔY reducible graphs are the graphs that can be reduced to a single vertex by Y-Δ transforms, 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
Rhombic dodecahedron
In geometry, the rhombic dodecahedron is a convex polyhedron with 12 rhombic faces. It is an Archimedean dual solid, or a Catalan solid. Its dual is the cuboctahedron.-Properties:...
. There also exist linkless graphs that cannot be transformed into an apex graph by Y-Δ transforms, removal of isolated vertices and degree-one vertices, and compression of degree-two vertices: for instance, the ten-vertex crown graph
Crown graph
In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j...
has a linkless embedding, but cannot be transformed into an apex graph in this way.
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
Knot (mathematics)
In mathematics, a knot is an embedding of a circle in 3-dimensional Euclidean space, R3, considered up to continuous deformations . A crucial difference between the standard mathematical and conventional notions of a knot is that mathematical knots are closed—there are no ends to tie or untie on a...
. The graphs that do not have knotless embeddings include K7 and K3,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
3-manifold
In mathematics, a 3-manifold is a 3-dimensional manifold. The topological, piecewise-linear, and smooth categories are all equivalent in three dimensions, so little distinction is made in whether we are dealing with say, topological 3-manifolds, or smooth 3-manifolds.Phenomena in three dimensions...
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.
History
The question of whether K6 has a linkless or flat embedding was posed within the topologyTopology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
research community in the early 1970s by . Linkless embeddings were brought to the attention of the graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
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
Petersen family
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....
(including K6) do not have such embeddings. As observed, linklessly embeddable graphs are closed
Closure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under graph minors, from which it follows by the Robertson–Seymour theorem
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
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
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
apex graph
Apex 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. We say an apex, not the apex because an apex graph may have more than one apex...
s with n > 4 have exactly this many edges, and proved a matching upper bound on the more general class of K6-minor-free graphs. observed that Sachs' question about the chromatic number would be resolved by a proof of Hadwiger's conjecture
Hadwiger conjecture (graph theory)
In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph...
that any k-chromatic graph has as a minor a k-vertex complete graph. The proof by 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
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
linklessly embeddable graph is 3-edge-colorable
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
.
Linkless embeddings started being studied within the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s research community in the late 1980s through the works of and . Algorithmically, the problem of recognizing linkless and flat embeddable graphs was settled once the forbidden minor characterization was proven: an algorithm of 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 , 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
Fáry's theorem
In mathematics, 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...
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 segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s?