Editing Linkless embedding (section)

==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 graph]]s, and the graphs with μ ≤ 3 are the [[planar graph]]s. As {{harvtxt|Robertson|Seymour|Thomas|1993a}} conjectured and {{harvtxt|Lovász|Schrijver|1998}} proved, the graphs with μ ≤ 4 are exactly the linklessly embeddable graphs.

=== Apex graphs ===

[[File:Apex rhombic dodecahedron.svg|thumb|A linkless apex graph that is not YΔY reducible.]]
The planar graphs and the [[apex graph]]s are linklessly embeddable, as are the graphs obtained by [[YΔ- and ΔY-transformation]]s from these graphs.<ref name="rst93a"/> 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]].<ref>{{harvtxt|Truemper|1992}}.</ref> 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.<ref name="rst93a"/>

=== Knotless graphs ===
[[File:Blue_Trefoil_Knot.png|thumb|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 (mathematics)|knot]]. The graphs that do not have knotless embeddings (that is, they are ''intrinsically knotted'') include ''K''<sub>7</sub> and ''K''<sub>3,3,1,1</sub>.<ref>{{harvtxt|Conway|Gordon|1983}}; {{harvtxt|Foisy|2002}}.</ref> 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.<ref>{{harvtxt|Foisy|2003}}.</ref>

One may also define graph families by the presence or absence of more complex knots and links in their embeddings,<ref>{{harvtxt|Nešetřil|Thomas|1985}}; {{harvtxt|Fleming|Diesl|2005}}.</ref> or by linkless embedding in [[3-manifold|three-dimensional manifolds]] other than Euclidean space.<ref>{{harvtxt|Flapan|Howards|Lawrence|Mellor|2006}}</ref> {{harvtxt|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 ''K''<sub>9</sub> is not intrinsically triple linked, but ''K''<sub>10</sub> is.<ref>For additional examples of intrinsically triple linked graphs, see {{harvtxt|Bowlin|Foisy|2004}}.</ref> 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''.<ref>{{harvtxt|Flapan|Pommersheim|Foisy|Naimi|2001}}</ref>