Linkless embedding

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 graph K6, 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]

  1. ^ a b Sachs (1983).
  2. ^ a b c Cite error: The named reference rst93a was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference nt85 was invoked but never defined (see the help page).
  4. ^ Robertson, Seymour & Thomas (1995).
  5. ^ Cite error: The named reference kkm10 was invoked but never defined (see the help page).