Linkless Embedding - Examples and Counterexamples

Examples and Counterexamples

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