linkless embedding

File:Hopf Link.png.]]

When the circle is mapped to three-dimensional Euclidean space by an injective function (a continuous function that does not map two different points of the circle to the same point of space), its image is a closed curve.

Two disjoint closed curves that both lie on the same plane are unlinked, and more generally a pair of disjoint closed curves is said to be unlinked when there is a continuous deformation of space that moves them both onto the same plane, without either curve passing through the other or through itself. If there is no such continuous motion, the two curves are said to be linked. For example, the Hopf link is formed by two circles that each pass through the disk spanned by the other. It forms the simplest example of a pair of linked curves, but it is possible for curves to be linked in other more complicated ways. If two curves are not linked, then it is possible to find a topological disk in space, having the first curve as its boundary and disjoint from the second curve. Conversely if such a disk exists then the curves are necessarily unlinked.

The linking number of two closed curves in three-dimensional space is a topological invariant of the curves: it is a number, defined from the curves in any of several equivalent ways, that does not change if the curves are moved continuously without passing through each other. The version of the linking number used for defining linkless embeddings of graphs is found by projecting the embedding onto the plane and counting the number of crossings of the projected embedding in which the first curve passes over the second one, modulo 2.{{harvtxt|Robertson|Seymour|Thomas|1993a}}. The projection must be "regular", meaning that no two vertices project to the same point, no vertex projects to the interior of an edge, and at every point of the projection where the projections of two edges intersect, they cross transversally; with this restriction, any two projections lead to the same linking number.

The linking number of the unlink is zero, and therefore, if a pair of curves has nonzero linking number, the two curves must be linked. However, there are examples of curves that are linked but that have zero linking number, such as the Whitehead link.

An embedding of a graph into three-dimensional space consists of a mapping from the vertices of the graph to points in space, and from the edges of the graph to curves in space, such that each endpoint of each edge is mapped to an endpoint of the corresponding curve, and such that the curves for two different edges do not intersect except at a common endpoint of the edges.

Any finite graph has a finite (though perhaps exponential) number of distinct simple cycles, and if the graph is embedded into three-dimensional space then each of these cycles forms a simple closed curve. One may compute the linking number of each disjoint pair of curves formed in this way; if all pairs of cycles have zero linking number, the embedding is said to be linkless.{{harvtxt|Conway|Gordon|1983}}; {{harvtxt|Sachs|1983}}; {{harvtxt|Robertson|Seymour|Thomas|1993a}}.

In some cases, a graph may be embedded in space in such a way that, for each cycle in the graph, one can find a disk bounded by that cycle that does not cross any other feature of the graph. In this case, the cycle must be unlinked from all the other cycles disjoint from it in the graph. The embedding is said to be flat if every cycle bounds a disk in this way.{{harvtxt|Robertson|Seymour|Thomas|1993a}}. A similar definition of a "good embedding" appears in {{harvtxt|Motwani|Raghunathan|Saran|1988}}; see also {{harvtxt|Saran|1989}} and {{harvtxt|Böhme|1990}}. A flat embedding is necessarily linkless, but there may exist linkless embeddings that are not flat: for instance, if G is a graph formed by two disjoint cycles, and it is embedded to form the Whitehead link, then the embedding is linkless but not flat.

A graph is said to be intrinsically linked if, no matter how it is embedded, the embedding is always linked. Although linkless and flat embeddings are not the same, the graphs that have linkless embeddings are the same as the graphs that have flat embeddings.{{harvtxt|Robertson|Seymour|Thomas|1993b}}.

File:Petersen family.svg.]]

As {{harvtxt|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 flatly and linklessly into space: every flat embedding can be continuously deformed to lie on a flat plane. And conversely, every nonplanar linkless graph has multiple linkless embeddings.

File:Apex graph.svg. If the planar part of the graph is embedded on a flat plane in space, and the apex vertex is placed above the plane and connected to it by straight line segments, the resulting embedding is flat.]]

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Δ- and ΔY-transformations 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 a YΔ-transformation, adding multiple copies of the resulting triangle edges, and then performing the reverse ΔY-transformations.

If a graph G has a linkless or flat embedding, then every minor of G (a graph formed by contraction of edges and deletion of edges and vertices) also has a linkless or flat embedding. Deletions cannot destroy the flatness of an embedding, and a contraction can be performed by leaving one endpoint of the contracted edge in place and rerouting all the edges incident to the other endpoint along the path of the contracted edge. Therefore, by the Robertson–Seymour theorem, the linklessly embeddable graphs have a forbidden graph characterization as the graphs that do not contain any of a finite set of minors.{{harvtxt|Nešetřil|Thomas|1985}}

The set of forbidden minors for the linklessly embeddable graphs was identified by {{harvtxt|Sachs|1983}}: the seven graphs of the Petersen family are all minor-minimal intrinsically linked graphs. However, Sachs was unable to prove that these were the only minimal linked graphs, and this was finally accomplished by {{harvtxt|Robertson|Seymour|Thomas|1995}}.

The forbidden minor characterization of linkless graphs leads to a polynomial time algorithm for their recognition, but not for actually constructing an embedding. {{harvtxt|Kawarabayashi|Kreutzer|Mohar|2010}} described a linear time algorithm that tests whether a graph is linklessly embeddable and, if so, constructs a flat embedding of the graph. Their algorithm finds large planar subgraphs within the given graph such that, if a linkless embedding exists, it has to respect the planar embedding of the subgraph. By repeatedly simplifying the graph whenever such a subgraph is found, they reduce the problem to one in which the remaining graph has bounded treewidth, at which point it can be solved by dynamic programming.

The problem of efficiently testing whether a given embedding is flat or linkless was posed by {{harvtxt|Robertson|Seymour|Thomas|1993a}}. It remains unsolved, and is equivalent in complexity to unknotting problem, the problem of testing whether a single curve in space is unknotted.{{harvtxt|Kawarabayashi|Kreutzer|Mohar|2010}} Testing unknottedness (and therefore, also, testing linklessness of an embedding) is known to be in NP but is not known to be NP-complete.{{harvtxt|Hass|Lagarias|Pippenger|1999}}.

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

File:Apex rhombic dodecahedron.svg

The planar graphs and the apex graphs are linklessly embeddable, as are the graphs obtained by YΔ- and ΔY-transformations from these graphs. 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.{{harvtxt|Truemper|1992}}. 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.

File:Blue_Trefoil_Knot.png, 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. The graphs that do not have knotless embeddings (that is, they are intrinsically knotted) include K₇ and K_3,3,1,1.{{harvtxt|Conway|Gordon|1983}}; {{harvtxt|Foisy|2002}}. 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.{{harvtxt|Foisy|2003}}.

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

The question of whether K₆ 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₆) do not have such embeddings. As {{harvtxt|Nešetřil|Thomas|1985}} observed, linklessly embeddable graphs are closed under graph minors, 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}},As previously announced by {{harvtxt|Robertson|Seymour|Thomas|1993b}}. 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 4n − 10: maximal apex graphs with n > 4 have exactly this many edges, and {{harvtxt|Mader|1968}} proved a matching upper bound on the more general class of K₆-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'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 = 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₆ minor and is not linkless, and there exist linkless graphs such as K₅ that require five colors. The snark theorem implies that every cubic linklessly embeddable graph is 3-edge-colorable.

Linkless embeddings started being studied within the algorithms 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.The application of the Robertson–Seymour algorithm to this problem was noted by {{harvtxt|Fellows|Langston|1988}}. 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 edges imply the existence of a linkless or flat embedding in which the edges are straight line segments?

{{reflist|2}}

{{refbegin|2}}

• {{citation

| last = Böhme | first = Thomas

| contribution = On spatial representations of graphs

| editor-last = Bodendieck | editor-first = Rainer

| isbn = 978-3-411-14301-6

| location = Mannheim

| pages = 151–167

| publisher = Bibliographisches Institut, Wissenschaftsverlag

| title = Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner

| year = 1990}}. As cited by {{harvtxt|Robertson|Seymour|Thomas|1993a}}.

• {{citation

| last = Bothe | first = H.-G.

| id = New Scottish Book, Problem 876, 20.5.1972

| journal = Colloquium Mathematicum

| page = 163

| title = Problem P855

| volume = 28

| year = 1973}}. As cited by {{harvtxt|Sachs|1983}}.

• {{citation

| last1 = Bowlin | first1 = Garry

| last2 = Foisy | first2 = Joel

| doi = 10.1142/S0218216504003652

| issue = 8

| journal = Journal of Knot Theory and Its Ramifications

| pages = 1021–1028

| title = Some new intrinsically 3-linked graphs

| volume = 13

| year = 2004| url = https://zenodo.org/record/894516

}}.

• {{citation

| last1 = Conway | first1 = John H. | author1-link = John Horton Conway

| last2 = Gordon | first2 = Cameron McA. | author2-link = Cameron Gordon (mathematician)

| doi = 10.1002/jgt.3190070410

| issue = 4

| journal = Journal of Graph Theory

| pages = 445–453

| title = Knots and links in spatial graphs

| volume = 7

| year = 1983}}.

• {{citation

| last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows

| last2 = Langston | first2 = Michael A. | author2-link = Michael Langston

| doi = 10.1145/44483.44491

| issue = 3

| journal = Journal of the ACM

| pages = 727–739

| title = Nonconstructive tools for proving polynomial-time decidability

| volume = 35

| year = 1988| doi-access = free

}}.

• {{citation

| last1 = Flapan | first1 = Erica | author1-link = Erica Flapan

| last2 = Howards | first2 = Hugh

| last3 = Lawrence | first3 = Don

| last4 = Mellor | first4 = Blake

| doi = 10.2140/agt.2006.6.1025

| journal = Algebraic & Geometric Topology

| pages = 1025–1035

| title = Intrinsic linking and knotting of graphs in arbitrary 3–manifolds

| volume = 6

| year = 2006

| issue = 3 | arxiv = math/0508004}}.

• {{citation

| last1 = Flapan | first1 = Erica | author1-link = Erica Flapan

| last2 = Naimi | first2 = Ramin

| last3 = Pommersheim | first3 = James

| doi = 10.1016/S0166-8641(00)00064-X

| issue = 2

| journal = Topology and Its Applications

| pages = 239–246

| title = Intrinsically triple linked complete graphs

| url = http://pages.pomona.edu/~elf04747/Research/I3L.pdf

| volume = 115

| year = 2001| doi-access = free

}}.

• {{citation

| last1 = Flapan | first1 = Erica | author1-link = Erica Flapan

| last2 = Pommersheim | first2 = James

| last3 = Foisy | first3 = Joel

| last4 = Naimi | first4 = Ramin

| doi = 10.1142/S0218216501001360

| issue = 8

| journal = Journal of Knot Theory and Its Ramifications

| pages = 1143–1154

| title = Intrinsically n-linked graphs

| volume = 10

| year = 2001}}.

• {{citation

| last1 = Fleming | first1 = Thomas

| last2 = Diesl | first2 = Alexander

| journal = Algebraic & Geometric Topology

| pages = 1419–1432

| title = Intrinsically linked graphs and even linking number

| volume = 5

| year = 2005

| issue = 4

| arxiv = math/0511133

| doi = 10.2140/agt.2005.5.1419}}.

• {{citation

| last = Foisy | first = Joel

| doi = 10.1002/jgt.10017

| issue = 3

| journal = Journal of Graph Theory

| pages = 178–187

| title = Intrinsically knotted graphs

| volume = 39

| year = 2002}}.

• {{citation

| last = Foisy | first = Joel

| doi = 10.1002/jgt.10114

| issue = 3

| journal = Journal of Graph Theory

| pages = 199–209

| title = A newly recognized intrinsically knotted graph

| volume = 43

| year = 2003}}.

• {{citation

| last1 = Hass | first1 = Joel | author1-link = Joel Hass

| last2 = Lagarias | first2 = Jeffrey C. | author2-link = Jeffrey Lagarias

| last3 = Pippenger | first3 = Nicholas | author3-link = Nick Pippenger

| doi = 10.1145/301970.301971

| issue = 2

| journal = Journal of the ACM

| pages = 185–211

| title = The computational complexity of knot and link problems

| volume = 46

| year = 1999

| arxiv = math/9807016}}.

• {{citation

| last = van der Holst | first = Hein

| doi = 10.1016/j.jctb.2008.10.002

| issue = 2

| journal = Journal of Combinatorial Theory, Series B

| pages = 512–530

| title = A polynomial-time algorithm to find a linkless embedding of a graph

| volume = 99

| year = 2009| doi-access =

}}.

• {{citation

| last1 = Kawarabayashi | first1 = Ken-ichi | authorlink = Ken-ichi Kawarabayashi

| last2 = Kreutzer | first2 = Stephan

| last3 = Mohar | first3 = Bojan | author3-link = Bojan Mohar

| contribution = Linkless and flat embeddings in 3-space and the unknot problem

| doi = 10.1145/1810959.1810975

| pages = 97–106

| title = Proc. ACM Symposium on Computational Geometry (SoCG '10)

| year = 2010| isbn = 978-1-4503-0016-2 }}.

• {{citation

| last1 = Lovász | first1 = László | author1-link = László Lovász

| last2 = Schrijver | first2 = Alexander | author2-link = Alexander Schrijver

| doi = 10.1090/S0002-9939-98-04244-0

| issue = 5

| journal = Proceedings of the American Mathematical Society

| pages = 1275–1285

| title = A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs

| volume = 126

| year = 1998| doi-access = free

}}.

• {{citation

| last = Mader | first = W.

| doi = 10.1007/BF01350657

| issue = 2

| journal = Mathematische Annalen

| pages = 154–168

| title = Homomorphiesätze für Graphen

| volume = 178

| year = 1968}}.

• {{citation

| last1 = Motwani | first1 = Rajeev | author1-link = Rajeev Motwani

| last2 = Raghunathan | first2 = Arvind

| last3 = Saran | first3 = Huzur

| contribution = Constructive results from graph minors: linkless embeddings

| doi = 10.1109/SFCS.1988.21956

| pages = 398–409

| title = Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS '88)

| year = 1988| isbn = 0-8186-0877-3 }}.

• {{citation

|last1 = Nešetřil

|first1 = Jaroslav

|author1-link = Jaroslav Nešetřil

|last2 = Thomas

|first2 = Robin

|author2-link = Robin Thomas (mathematician)

|issue = 4

|journal = Commentationes Mathematicae Universitatis Carolinae

|pages = 655–659

|title = A note on spatial representation of graphs

|url = http://dspace.dml.cz/handle/10338.dmlcz/106404

|volume = 26

|year = 1985

|url-status = dead

|archiveurl = https://web.archive.org/web/20110718171201/http://dspace.dml.cz/handle/10338.dmlcz/106404

|archivedate = 2011-07-18

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| doi = 10.1006/jctb.1995.1006

| issue = 1

| journal = Journal of Combinatorial Theory, Series B

| pages = 65–110

| title = Graph Minors. XIII. The disjoint paths problem

| volume = 63

| year = 1995| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)

| contribution = A survey of linkless embeddings

| editor1-last = Robertson | editor1-first = Neil | editor1-link = Neil Robertson (mathematician)

| editor2-last = Seymour | editor2-first = Paul | editor2-link = Paul Seymour (mathematician)

| pages = 125–136

| publisher = American Mathematical Society

| series = Contemporary Mathematics

| title = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors

| url = http://people.math.gatech.edu/~thomas/PAP/linklsurvey.pdf

| volume = 147

| year = 1993a}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)

| doi = 10.1090/S0273-0979-1993-00335-5

| issue = 1

| journal = Bulletin of the American Mathematical Society

| pages = 84–89

| title = Linkless embeddings of graphs in 3-space

| volume = 28

| year = 1993b

| arxiv = math/9301216

| mr = 1164063}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)

| doi = 10.1006/jctb.1995.1032

| issue = 2

| journal = Journal of Combinatorial Theory, Series B

| pages = 185–227

| title = Sachs' linkless embedding conjecture

| volume = 64

| year = 1995| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)

| doi = 10.1007/BF01202354

| issue = 3

| journal = Combinatorica

| pages = 279–361

| title = Hadwiger's conjecture for K₆-free graphs

| url = http://people.math.gatech.edu/~thomas/PAP/hadwiger.pdf

| volume = 13

| year = 1993c}}.

• {{citation

| last = Sachs | first = Horst | author-link = Horst Sachs

| contribution = On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem

| doi = 10.1007/BFb0071633

| editor1-last = Horowiecki | editor1-first = M.

| editor2-last = Kennedy | editor2-first = J. W.

| editor3-last = Sysło | editor3-first = M. M.

| pages = 230–241

| publisher = Springer-Verlag

| series = Lecture Notes in Mathematics

| title = Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981

| volume = 1018

| isbn = 978-3-540-12687-4 | year = 1983}}.

• {{citation

| last = Saran | first = Huzur

| publisher = University of California, Berkeley

| series = Ph.D. thesis

| title = Constructive Results in Graph Minors: Linkless Embeddings

| year = 1989}}.

• {{citation

| last = Truemper | first = Klaus

| pages = 100–101

| publisher = Academic Press

| title = Matroid Decomposition

| url = http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf

| year = 1992}}.

{{refend}}

{{refbegin}}

• {{citation|last=Ramírez Alfonsín|first=J. L.|title=Knots and links in spatial graphs: a survey|journal=Discrete Mathematics|year=2005|volume=302|issue=1–3|pages=225–242|doi=10.1016/j.disc.2004.07.035|doi-access=}}.

{{refend}}

Category:Topological graph theory

Category:Knot theory

Category:Graph minor theory