Editing Linkless embedding (section)

{{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 [[graph embedding|embedding]] of the graph into three-dimensional [[Euclidean space]] in such a way that no two [[Cycle (graph theory)|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 (mathematics)|disk]] whose interior is [[Disjoint sets|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 graph]]s.<ref name="s83">{{harvtxt|Sachs|1983}}.</ref> Complementarily, an '''intrinsically linked graph''' is a graph that does not have a linkless embedding.

Flat embeddings are automatically linkless, but not vice versa.<ref name="rst93a"/> The [[complete graph]] {{math|''K''{{sub|6}}}}, the [[Petersen graph]], and the other five graphs in the [[Petersen family]] do not have linkless embeddings.<ref name="s83"/> Every [[graph minor]] of a linklessly embeddable graph is again linklessly embeddable,<ref name="nt85"/> as is every graph that can be reached from a linklessly embeddable graph by [[YΔ- and ΔY-transformations]].<ref name="rst93a"/> The linklessly embeddable graphs have the [[Petersen family]] graphs as their [[forbidden minor]]s,<ref>{{harvtxt|Robertson|Seymour|Thomas|1995}}.</ref> and include the planar graphs and [[apex graph]]s.<ref name="rst93a"/> They may be recognized, and a flat embedding may be constructed for them, in {{math|''O''(''n''{{sup|2}})}}.<ref name="kkm10"/>