Editing Linkless embedding (section)

==History==
The question of whether ''K''<sub>6</sub> has a linkless or flat embedding was posed within the [[topology]] research community in the early 1970s by {{harvtxt|Bothe|1973}}. Linkless embeddings were brought to the attention of the [[graph theory]] community by {{harvs|first=Horst|last=Sachs|authorlink=Horst Sachs|year=1983|txt}}, 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 ''K''<sub>6</sub>) do not have such embeddings. As {{harvtxt|Nešetřil|Thomas|1985}} observed, linklessly embeddable graphs are [[closure (mathematics)|closed]] under [[graph minor]]s, 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 {{harvtxt|Robertson|Seymour|Thomas|1995}},<ref>As previously announced by {{harvtxt|Robertson|Seymour|Thomas|1993b}}.</ref> 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.

{{harvtxt|Sachs|1983}} 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 4''n''&nbsp;&minus;&nbsp;10: [[maximal element|maximal]] [[apex graph]]s with ''n''&nbsp;>&nbsp;4 have exactly this many edges,<ref name="s83"/> and {{harvtxt|Mader|1968}} proved a matching upper bound on the more general class of ''K''<sub>6</sub>-minor-free graphs. {{harvtxt|Nešetřil|Thomas|1985}} observed that Sachs' question about the chromatic number would be resolved by a proof of [[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]] that any ''k''-chromatic graph has as a minor a ''k''-vertex complete graph. The proof by {{harvtxt|Robertson|Seymour|Thomas|1993c}} of the case ''k''&nbsp;=&nbsp;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 ''K''<sub>6</sub> minor and is not linkless, and there exist linkless graphs such as ''K''<sub>5</sub> that require five colors. The [[snark theorem]] implies that every [[cubic graph|cubic]] linklessly embeddable graph is [[edge coloring|3-edge-colorable]].

Linkless embeddings started being studied within the [[algorithm]]s research community in the late 1980s through the works of {{harvtxt|Fellows|Langston|1988}} and {{harvtxt|Motwani|Raghunathan|Saran|1988}}. Algorithmically, the problem of recognizing linkless and flat embeddable graphs was settled once the forbidden minor characterization was proven: an algorithm of {{harvtxt|Robertson|Seymour|1995}} can be used to test in [[polynomial time]] whether a given graph contains any of the seven forbidden minors.<ref>The application of the Robertson–Seymour algorithm to this problem was noted by {{harvtxt|Fellows|Langston|1988}}.</ref> This method does not construct linkless or flat embeddings when they exist, but an algorithm that does construct an embedding was developed by {{harvtxt|van der Holst|2009}}, and a more efficient [[linear time]] algorithm was found by {{harvtxt|Kawarabayashi|Kreutzer|Mohar|2010}}.

A final question of {{harvtxt|Sachs|1983}} 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 function|piecewise linear]] edges imply the existence of a linkless or flat embedding in which the edges are straight [[line segment]]s?