165:. 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.
300:, 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.
443:
480:
226:
335:(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
285:
130:
193:; 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
624:
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
161:, 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
200:
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
280:
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
369:
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
208:
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
179:
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
462:
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
205:, 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.
629:, 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.
418:. 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
216:
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.
467:. 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
188:
2. 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
241:
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
513:. 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.
742:
whether a given graph contains any of the seven forbidden minors. This method does not construct linkless or flat embeddings when they exist, but an algorithm that does construct an embedding was developed by
292:. 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.
303:
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
209:
embedding is said to be flat if every cycle bounds a disk in this way. A flat embedding is necessarily linkless, but there may exist linkless embeddings that are not flat: for instance, if
693: = 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
389:, the problem of testing whether a single curve in space is unknotted. Testing unknottedness (and therefore, also, testing linklessness of an embedding) is known to be in
354:
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
491:
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
1484:
734:. Algorithmically, the problem of recognizing linkless and flat embeddable graphs was settled once the forbidden minor characterization was proven: an algorithm of
1658:
1284:
315:
of vertices by performing a YΔ-transformation, adding multiple copies of the resulting triangle edges, and then performing the reverse ΔY-transformations.
307:
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
370:
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
201:
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
1710:
1588:
1430:
1784:(1983), "On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem", in Horowiecki, M.; Kennedy, J. W.; Sysło, M. M. (eds.),
516:
One may also define graph families by the presence or absence of more complex knots and links in their embeddings, or by linkless embedding in
1086:
94:
of a linklessly embeddable graph is again linklessly embeddable, as is every graph that can be reached from a linklessly embeddable graph by
524:
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
411:
550:-component link that cannot be separated by a topological sphere into two separated parts; minor-minimal graphs that are intrinsically
674:
213:
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.
1866:
1307:
1213:
594:
340:
311:
planar graph (one in which all vertices have exactly three neighbors, such as the cube) it is possible to make duplicates of any
95:
766:
for linkless graphs appears not to have been answered: when does the existence of a linkless or flat embedding with curved or
455:
304:
1733:
1697:
1645:
1623:
1611:
1579:
1150:
312:
181:
1558:
621:
336:
1211:; Howards, Hugh; Lawrence, Don; Mellor, Blake (2006), "Intrinsic linking and knotting of graphs in arbitrary 3–manifolds",
1256:
1741:
1737:
1705:
1701:
1653:
1649:
1627:
1619:
1615:
1583:
1554:
190:
153:(a continuous function that does not map two different points of the circle to the same point of space), its image is a
1876:
767:
1482:(1998), "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs",
257:
20:
1550:
1363:
1340:
1155:
176:
1533:; Raghunathan, Arvind; Saran, Huzur (1988), "Constructive results from graph minors: linkless embeddings",
1451:
415:
1475:
1509:
613:
463:
reducible, such as the apex graph formed by connecting an apex vertex to every degree-three vertex of a
59:
is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the
1871:
763:
464:
328:
202:
40:
1812:
1479:
1428:
van der Holst, Hein (2009), "A polynomial-time algorithm to find a linkless embedding of a graph",
375:
1667:
1406:
1397:
1316:
1305:
Fleming, Thomas; Diesl, Alexander (2005), "Intrinsically linked graphs and even linking number",
1222:
1185:
1146:
492:
386:
185:
162:
150:
48:
1082:
419:
381:
The problem of efficiently testing whether a given embedding is flat or linkless was posed by
1844:
1789:
1769:
1719:
1677:
1631:
1597:
1538:
1518:
1493:
1463:
1439:
1416:
1388:
1372:
1349:
1326:
1293:
1265:
1232:
1194:
1180:
1164:
1134:
783:
636:
28:
1689:
1633:
Graph
Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
1077:
Böhme, Thomas (1990), "On spatial representations of graphs", in
Bodendieck, Rainer (ed.),
597:
of the graphs with linkless and flat embeddings; Sachs showed that the seven graphs of the
442:
1685:
1639:, Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 125–136
1176:
770:
edges imply the existence of a linkless or flat embedding in which the edges are straight
739:
648:
598:
390:
362:
351:
230:
146:
103:
99:
87:
36:
32:
1745:
1282:; Pommersheim, James; Foisy, Joel; Naimi, Ramin (2001), "Intrinsically n-linked graphs",
673:
observed that Sachs' question about the chromatic number would be resolved by a proof of
1530:
1392:
253:
243:
194:
169:
83:
71:
1270:
1860:
1786:
Graph Theory: Proceedings of a
Conference held in Łagów, Poland, February 10–13, 1981
1760:
1248:
1119:
716:
708:
52:
1681:
471:
has a linkless embedding, but cannot be transformed into an apex graph in this way.
47:
is an embedding with the property that every cycle is the boundary of a topological
1788:, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 230–241,
1279:
1244:
1208:
771:
582:
423:
346:
The set of forbidden minors for the linklessly embeddable graphs was identified by
277:
154:
60:
1498:
1570:
365:
algorithm for their recognition, but not for actually constructing an embedding.
1781:
1455:
1059:
The application of the
Robertson–Seymour algorithm to this problem was noted by
748:
712:
617:
586:
479:
468:
394:
308:
184:
of the projected embedding in which the first curve passes over the second one,
91:
1848:
1835:
Ramírez Alfonsín, J. L. (2005), "Knots and links in spatial graphs: a survey",
1443:
1081:, Mannheim: Bibliographisches Institut, Wissenschaftsverlag, pp. 151–167,
110:. They may be recognized, and a flat embedding may be constructed for them, in
1297:
1138:
651:
517:
451:
297:
289:
225:
107:
1542:
1467:
1384:
1330:
1236:
723:
434:
proved, the graphs with μ ≤ 4 are exactly the linklessly embeddable graphs.
371:
134:
1724:
1602:
1168:
1458:(2010), "Linkless and flat embeddings in 3-space and the unknot problem",
1420:
1183:(1988), "Nonconstructive tools for proving polynomial-time decidability",
593:), who posed several related problems including the problem of finding a
574:
173:
158:
1199:
1079:
Contemporary
Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner
1793:
1773:
1535:
Proc. 29th IEEE Symposium on
Foundations of Computer Science (FOCS '88)
1522:
484:
284:
1376:
1361:
Foisy, Joel (2003), "A newly recognized intrinsically knotted graph",
1353:
129:
1672:
1411:
1321:
1227:
495:. The graphs that do not have knotless embeddings (that is, they are
142:
70:
Flat embeddings are automatically linkless, but not vice versa. The
1022:
For additional examples of intrinsically triple linked graphs, see
700:
minor and is not linkless, and there exist linkless graphs such as
361:
The forbidden minor characterization of linkless graphs leads to a
1395:(1999), "The computational complexity of knot and link problems",
478:
441:
283:
224:
128:
343:
as the graphs that do not contain any of a finite set of minors.
157:. Two disjoint closed curves that both lie on the same plane are
1035:
1011:
662:
proved a matching upper bound on the more general class of
581:. Linkless embeddings were brought to the attention of the
1586:(1995), "Graph Minors. XIII. The disjoint paths problem",
876:
752:
726:
research community in the late 1980s through the works of
385:. It remains unsolved, and is equivalent in complexity to
366:
1803:
Constructive
Results in Graph Minors: Linkless Embeddings
639:
of linkless embeddable graphs. The number of edges in an
454:
are linklessly embeddable, as are the graphs obtained by
1460:
Proc. ACM Symposium on Computational Geometry (SoCG '10)
910:. A similar definition of a "good embedding" appears in
16:
Embedding a graph in 3D space with no cycles interlinked
1093:
1047:
931:
911:
907:
895:
835:
731:
686:
427:
382:
861:
626:
573:
has a linkless or flat embedding was posed within the
521:
355:
1656:(1993b), "Linkless embeddings of graphs in 3-space",
943:
722:
Linkless embeddings started being studied within the
635:
also asked for bounds on the number of edges and the
172:
of two closed curves in three-dimensional space is a
1338:
Foisy, Joel (2002), "Intrinsically knotted graphs",
658: > 4 have exactly this many edges, and
180:
embedding onto the plane and counting the number of
67:
is a graph that does not have a linkless embedding.
1563:
Commentationes Mathematicae Universitatis Carolinae
1805:, Ph.D. thesis, University of California, Berkeley
1507:Mader, W. (1968), "Homomorphiesätze für Graphen",
281:linkless graph has multiple linkless embeddings.
1708:(1995), "Sachs' linkless embedding conjecture",
1485:Proceedings of the American Mathematical Society
1108:: 163, New Scottish Book, Problem 876, 20.5.1972
735:
446:A linkless apex graph that is not YΔY reducible.
256:, the graph formed by removing an edge from the
1622:(1993a), "A survey of linkless embeddings", in
1060:
727:
431:
995:
850:
670:
609:
1659:Bulletin of the American Mathematical Society
1249:"Intrinsically triple linked complete graphs"
1153:(1983), "Knots and links in spatial graphs",
744:
406:Graphs with small Colin de Verdière invariant
327:has a linkless or flat embedding, then every
8:
1559:"A note on spatial representation of graphs"
1285:Journal of Knot Theory and Its Ramifications
1127:Journal of Knot Theory and its Ramifications
999:
967:
887:
98:. The linklessly embeddable graphs have the
1247:; Naimi, Ramin; Pommersheim, James (2001),
1023:
612:observed, linklessly embeddable graphs are
877:Kawarabayashi, Kreutzer & Mohar (2010)
753:Kawarabayashi, Kreutzer & Mohar (2010)
414:is an integer defined for any graph using
367:Kawarabayashi, Kreutzer & Mohar (2010)
339:, the linklessly embeddable graphs have a
1723:
1711:Journal of Combinatorial Theory, Series B
1671:
1601:
1589:Journal of Combinatorial Theory, Series B
1497:
1431:Journal of Combinatorial Theory, Series B
1410:
1320:
1269:
1226:
1198:
577:research community in the early 1970s by
1120:"Some new intrinsically 3-linked graphs"
955:
831:
829:
827:
825:
823:
821:
819:
817:
815:
531:is not intrinsically triple linked, but
1094:Robertson, Seymour & Thomas (1993a)
1048:Robertson, Seymour & Thomas (1993b)
932:Robertson, Seymour & Thomas (1993b)
912:Motwani, Raghunathan & Saran (1988)
908:Robertson, Seymour & Thomas (1993a)
896:Robertson, Seymour & Thomas (1993a)
872:
870:
836:Robertson, Seymour & Thomas (1993a)
794:
732:Motwani, Raghunathan & Saran (1988)
687:Robertson, Seymour & Thomas (1993c)
428:Robertson, Seymour & Thomas (1993a)
383:Robertson, Seymour & Thomas (1993a)
90:do not have linkless embeddings. Every
862:Robertson, Seymour & Thomas (1995)
846:
844:
627:Robertson, Seymour & Thomas (1995)
538:is. More generally, one can define an
522:Flapan, Naimi & Pommersheim (2001)
356:Robertson, Seymour & Thomas (1995)
1111:
1100:Bothe, H.-G. (1973), "Problem P855",
983:
971:
944:Hass, Lagarias & Pippenger (1999)
919:
915:
891:
806:
802:
800:
798:
762:on the possibility of an analogue of
759:
685:-vertex complete graph. The proof by
659:
632:
590:
578:
374:, at which point it can be solved by
347:
238:
7:
546:to be an embedding that contains an
422:, and the graphs with μ ≤ 3 are the
266:, and the complete tripartite graph
106:, and include the planar graphs and
35:of the graph into three-dimensional
1118:Bowlin, Garry; Foisy, Joel (2004),
643:-vertex linkless graph is at most 4
86:, and the other five graphs in the
1820:, Academic Press, pp. 100–101
1308:Algebraic & Geometric Topology
1214:Algebraic & Geometric Topology
681:-chromatic graph has as a minor a
608:) do not have such embeddings. As
14:
412:Colin de Verdière graph invariant
595:forbidden graph characterization
341:forbidden graph characterization
319:Characterization and recognition
1682:10.1090/S0273-0979-1993-00335-5
715:linklessly embeddable graph is
620:, from which it follows by the
487:, the simplest nontrivial knot.
145:is mapped to three-dimensional
23:, a mathematical discipline, a
736:Robertson & Seymour (1995)
707:that require five colors. The
1:
1499:10.1090/S0002-9939-98-04244-0
1271:10.1016/S0166-8641(00)00064-X
1257:Topology and its Applications
1061:Fellows & Langston (1988)
728:Fellows & Langston (1988)
432:Lovász & Schrijver (1998)
1569:(4): 655–659, archived from
996:Nešetřil & Thomas (1985)
851:Nešetřil & Thomas (1985)
671:Nešetřil & Thomas (1985)
610:Nešetřil & Thomas (1985)
520:other than Euclidean space.
221:Examples and counterexamples
133:Two linked curves forming a
1746:"Hadwiger's conjecture for
1046:As previously announced by
518:three-dimensional manifolds
57:linklessly embeddable graph
43:of the graph are linked. A
1893:
1849:10.1016/j.disc.2004.07.035
1444:10.1016/j.jctb.2008.10.002
1000:Fleming & Diesl (2005)
968:Conway & Gordon (1983)
888:Conway & Gordon (1983)
554:-linked are known for all
542:-linked embedding for any
456:YΔ- and ΔY-transformations
450:The planar graphs and the
401:Related families of graphs
350:: the seven graphs of the
305:YΔ- and ΔY-transformations
96:YΔ- and ΔY-transformations
65:intrinsically linked graph
39:in such a way that no two
1298:10.1142/S0218216501001360
1139:10.1142/S0218216504003652
1024:Bowlin & Foisy (2004)
622:Robertson–Seymour theorem
483:A closed curve forming a
337:Robertson–Seymour theorem
1867:Topological graph theory
1811:Truemper, Klaus (1992),
625:were finally settled by
566:The question of whether
258:complete bipartite graph
21:topological graph theory
1543:10.1109/SFCS.1988.21956
1468:10.1145/1810959.1810975
1452:Kawarabayashi, Ken-ichi
1364:Journal of Graph Theory
1341:Journal of Graph Theory
1331:10.2140/agt.2005.5.1419
1237:10.2140/agt.2006.6.1025
1156:Journal of Graph Theory
1102:Colloquium Mathematicum
751:algorithm was found by
747:, and a more efficient
738:can be used to test in
647: − 10:
458:from these graphs. The
393:but is not known to be
1725:10.1006/jctb.1995.1032
1603:10.1006/jctb.1995.1006
1169:10.1002/jgt.3190070410
488:
447:
416:algebraic graph theory
293:
234:
138:
63:. Complementarily, an
1814:Matroid Decomposition
1801:Saran, Huzur (1989),
1510:Mathematische Annalen
1454:; Kreutzer, Stephan;
1421:10.1145/301970.301971
675:Hadwiger's conjecture
497:intrinsically knotted
482:
445:
287:
228:
132:
1837:Discrete Mathematics
1537:, pp. 398–409,
1480:Schrijver, Alexander
1389:Lagarias, Jeffrey C.
1181:Langston, Michael A.
1151:Gordon, Cameron McA.
1036:Flapan et al. (2001)
1012:Flapan et al. (2006)
758:A final question of
745:van der Holst (2009)
669:-minor-free graphs.
465:rhombic dodecahedron
460:YΔY reducible graphs
1462:, pp. 97–106,
1393:Pippenger, Nicholas
1200:10.1145/44483.44491
1177:Fellows, Michael R.
711:implies that every
376:dynamic programming
1877:Graph minor theory
1794:10.1007/BFb0071633
1774:10.1007/BF01202354
1551:Nešetřil, Jaroslav
1523:10.1007/BF01350657
1398:Journal of the ACM
1186:Journal of the ACM
489:
448:
420:outerplanar graphs
387:unknotting problem
294:
235:
151:injective function
139:
55:from the graph. A
51:whose interior is
25:linkless embedding
1377:10.1002/jgt.10114
1354:10.1002/jgt.10017
1088:978-3-411-14301-6
1884:
1851:
1843:(1–3): 225–242,
1821:
1819:
1806:
1796:
1776:
1757:
1728:
1727:
1692:
1675:
1640:
1638:
1606:
1605:
1574:
1545:
1525:
1502:
1501:
1492:(5): 1275–1285,
1470:
1446:
1423:
1414:
1379:
1356:
1333:
1324:
1300:
1292:(8): 1143–1154,
1274:
1273:
1253:
1239:
1230:
1203:
1202:
1171:
1141:
1133:(8): 1021–1028,
1124:
1109:
1091:
1064:
1057:
1051:
1044:
1038:
1033:
1027:
1020:
1014:
1009:
1003:
993:
987:
981:
975:
965:
959:
953:
947:
941:
935:
929:
923:
905:
899:
885:
879:
874:
865:
859:
853:
848:
839:
833:
810:
804:
784:Knots and graphs
768:piecewise linear
717:3-edge-colorable
637:chromatic number
430:conjectured and
120:
104:forbidden minors
102:graphs as their
81:
29:undirected graph
1892:
1891:
1887:
1886:
1885:
1883:
1882:
1881:
1857:
1856:
1855:
1834:
1830:
1828:Further reading
1825:
1817:
1810:
1800:
1780:
1755:
1752:
1734:Robertson, Neil
1732:
1698:Robertson, Neil
1696:
1646:Robertson, Neil
1644:
1636:
1624:Robertson, Neil
1612:Robertson, Neil
1610:
1580:Robertson, Neil
1578:
1549:
1531:Motwani, Rajeev
1529:
1506:
1474:
1450:
1427:
1383:
1360:
1337:
1304:
1278:
1251:
1243:
1207:
1175:
1147:Conway, John H.
1145:
1122:
1117:
1099:
1089:
1076:
1072:
1067:
1058:
1054:
1045:
1041:
1034:
1030:
1021:
1017:
1010:
1006:
994:
990:
982:
978:
966:
962:
956:Truemper (1992)
954:
950:
942:
938:
930:
926:
906:
902:
886:
882:
875:
868:
860:
856:
849:
842:
834:
813:
805:
796:
792:
780:
740:polynomial time
706:
699:
668:
607:
599:Petersen family
587:Horst Sachs
572:
564:
537:
530:
512:
505:
477:
475:Knotless graphs
440:
408:
403:
363:polynomial time
352:Petersen family
321:
313:independent set
272:
265:
251:
231:Petersen family
223:
147:Euclidean space
127:
111:
100:Petersen family
88:Petersen family
80:
74:
37:Euclidean space
17:
12:
11:
5:
1890:
1888:
1880:
1879:
1874:
1869:
1859:
1858:
1854:
1853:
1831:
1829:
1826:
1824:
1823:
1808:
1798:
1778:
1768:(3): 279–361,
1750:
1730:
1718:(2): 185–227,
1702:Seymour, P. D.
1694:
1650:Seymour, P. D.
1642:
1608:
1576:
1547:
1527:
1517:(2): 154–168,
1504:
1476:Lovász, László
1472:
1448:
1438:(2): 512–530,
1425:
1405:(2): 185–211,
1381:
1371:(3): 199–209,
1358:
1348:(3): 178–187,
1335:
1302:
1276:
1264:(2): 239–246,
1241:
1205:
1193:(3): 727–739,
1173:
1163:(4): 445–453,
1143:
1115:
1110:. As cited by
1097:
1092:. As cited by
1087:
1073:
1071:
1068:
1066:
1065:
1052:
1039:
1028:
1015:
1004:
988:
976:
960:
948:
936:
924:
900:
880:
866:
854:
840:
811:
793:
791:
788:
787:
786:
779:
776:
764:Fáry's theorem
704:
697:
666:
605:
570:
563:
560:
535:
528:
510:
503:
476:
473:
439:
436:
407:
404:
402:
399:
320:
317:
270:
263:
254:Petersen graph
249:
244:complete graph
222:
219:
195:Whitehead link
170:linking number
126:
123:
84:Petersen graph
78:
72:complete graph
45:flat embedding
15:
13:
10:
9:
6:
4:
3:
2:
1889:
1878:
1875:
1873:
1870:
1868:
1865:
1864:
1862:
1850:
1846:
1842:
1838:
1833:
1832:
1827:
1816:
1815:
1809:
1804:
1799:
1795:
1791:
1787:
1783:
1779:
1775:
1771:
1767:
1763:
1762:
1761:Combinatorica
1754:
1753:-free graphs"
1749:
1743:
1742:Thomas, Robin
1739:
1738:Seymour, Paul
1735:
1731:
1726:
1721:
1717:
1713:
1712:
1707:
1706:Thomas, Robin
1703:
1699:
1695:
1691:
1687:
1683:
1679:
1674:
1669:
1665:
1661:
1660:
1655:
1654:Thomas, Robin
1651:
1647:
1643:
1635:
1634:
1629:
1628:Seymour, Paul
1625:
1621:
1620:Thomas, Robin
1617:
1616:Seymour, Paul
1613:
1609:
1604:
1599:
1596:(1): 65–110,
1595:
1591:
1590:
1585:
1584:Seymour, Paul
1581:
1577:
1573:on 2011-07-18
1572:
1568:
1564:
1560:
1556:
1555:Thomas, Robin
1552:
1548:
1544:
1540:
1536:
1532:
1528:
1524:
1520:
1516:
1512:
1511:
1505:
1500:
1495:
1491:
1487:
1486:
1481:
1477:
1473:
1469:
1465:
1461:
1457:
1453:
1449:
1445:
1441:
1437:
1433:
1432:
1426:
1422:
1418:
1413:
1408:
1404:
1400:
1399:
1394:
1390:
1386:
1382:
1378:
1374:
1370:
1366:
1365:
1359:
1355:
1351:
1347:
1343:
1342:
1336:
1332:
1328:
1323:
1318:
1315:: 1419–1432,
1314:
1310:
1309:
1303:
1299:
1295:
1291:
1287:
1286:
1281:
1280:Flapan, Erica
1277:
1272:
1267:
1263:
1259:
1258:
1250:
1246:
1245:Flapan, Erica
1242:
1238:
1234:
1229:
1224:
1221:: 1025–1035,
1220:
1216:
1215:
1210:
1209:Flapan, Erica
1206:
1201:
1196:
1192:
1188:
1187:
1182:
1178:
1174:
1170:
1166:
1162:
1158:
1157:
1152:
1148:
1144:
1140:
1136:
1132:
1128:
1121:
1116:
1113:
1107:
1103:
1098:
1095:
1090:
1084:
1080:
1075:
1074:
1069:
1062:
1056:
1053:
1049:
1043:
1040:
1037:
1032:
1029:
1025:
1019:
1016:
1013:
1008:
1005:
1001:
997:
992:
989:
985:
980:
977:
973:
969:
964:
961:
957:
952:
949:
945:
940:
937:
933:
928:
925:
921:
917:
913:
909:
904:
901:
897:
893:
889:
884:
881:
878:
873:
871:
867:
863:
858:
855:
852:
847:
845:
841:
837:
832:
830:
828:
826:
824:
822:
820:
818:
816:
812:
808:
803:
801:
799:
795:
789:
785:
782:
781:
777:
775:
773:
772:line segments
769:
765:
761:
756:
754:
750:
746:
741:
737:
733:
729:
725:
720:
718:
714:
710:
709:snark theorem
703:
696:
692:
688:
684:
680:
676:
672:
665:
661:
657:
653:
650:
646:
642:
638:
634:
630:
628:
623:
619:
615:
611:
604:
600:
596:
592:
588:
585:community by
584:
580:
576:
569:
561:
559:
557:
553:
549:
545:
541:
534:
527:
523:
519:
514:
509:
502:
498:
494:
486:
481:
474:
472:
470:
466:
461:
457:
453:
444:
437:
435:
433:
429:
425:
424:planar graphs
421:
417:
413:
405:
400:
398:
396:
392:
388:
384:
379:
377:
373:
368:
364:
359:
357:
353:
349:
344:
342:
338:
334:
330:
326:
318:
316:
314:
310:
306:
301:
299:
291:
286:
282:
279:
274:
269:
262:
259:
255:
248:
245:
240:
232:
227:
220:
218:
214:
212:
206:
204:
203:simple cycles
198:
196:
192:
191:transversally
187:
183:
178:
175:
171:
166:
164:
160:
156:
152:
148:
144:
136:
131:
124:
122:
118:
114:
109:
105:
101:
97:
93:
89:
85:
77:
73:
68:
66:
62:
61:planar graphs
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
1840:
1836:
1813:
1802:
1785:
1782:Sachs, Horst
1765:
1759:
1747:
1715:
1709:
1673:math/9301216
1666:(1): 84–89,
1663:
1657:
1632:
1593:
1587:
1571:the original
1566:
1562:
1534:
1514:
1508:
1489:
1483:
1459:
1456:Mohar, Bojan
1435:
1429:
1412:math/9807016
1402:
1396:
1368:
1362:
1345:
1339:
1322:math/0511133
1312:
1306:
1289:
1283:
1261:
1255:
1228:math/0508004
1218:
1212:
1190:
1184:
1160:
1154:
1130:
1126:
1112:Sachs (1983)
1105:
1101:
1078:
1055:
1042:
1031:
1018:
1007:
991:
984:Foisy (2003)
979:
972:Foisy (2002)
963:
951:
939:
927:
920:Böhme (1990)
916:Saran (1989)
903:
892:Sachs (1983)
883:
857:
807:Sachs (1983)
760:Sachs (1983)
757:
721:
701:
694:
690:
689:of the case
682:
678:
663:
660:Mader (1968)
655:
644:
640:
633:Sachs (1983)
631:
618:graph minors
602:
583:graph theory
579:Bothe (1973)
567:
565:
555:
551:
547:
543:
539:
532:
525:
515:
507:
500:
496:
490:
459:
449:
409:
380:
360:
348:Sachs (1983)
345:
332:
324:
322:
302:
295:
278:planar graph
275:
267:
260:
246:
239:Sachs (1983)
236:
215:
210:
207:
199:
167:
155:closed curve
140:
116:
112:
75:
69:
64:
56:
44:
24:
18:
1872:Knot theory
914:; see also
749:linear time
652:apex graphs
601:(including
469:crown graph
452:apex graphs
438:Apex graphs
395:NP-complete
323:If a graph
174:topological
125:Definitions
108:apex graphs
92:graph minor
1861:Categories
1385:Hass, Joel
1070:References
724:algorithms
499:) include
298:apex graph
290:apex graph
1744:(1993c),
677:that any
372:treewidth
182:crossings
177:invariant
141:When the
135:Hopf link
33:embedding
1630:(eds.),
1557:(1985),
778:See also
575:topology
159:unlinked
53:disjoint
1690:1164063
649:maximal
589: (
562:History
511:3,3,1,1
485:trefoil
1688:
1085:
616:under
614:closed
276:Every
252:, the
186:modulo
163:linked
149:by an
143:circle
82:, the
41:cycles
31:is an
27:of an
1818:(PDF)
1756:(PDF)
1668:arXiv
1637:(PDF)
1407:arXiv
1317:arXiv
1252:(PDF)
1223:arXiv
1123:(PDF)
790:Notes
713:cubic
654:with
426:. As
329:minor
309:cubic
271:3,3,1
1083:ISBN
918:and
730:and
591:1983
506:and
493:knot
410:The
229:The
168:The
49:disk
1845:doi
1841:302
1790:doi
1770:doi
1720:doi
1678:doi
1598:doi
1539:doi
1519:doi
1515:178
1494:doi
1490:126
1464:doi
1440:doi
1417:doi
1373:doi
1350:doi
1327:doi
1294:doi
1266:doi
1262:115
1233:doi
1195:doi
1165:doi
1135:doi
331:of
296:An
288:An
264:4,4
237:As
19:In
1863::
1839:,
1766:13
1764:,
1758:,
1740:;
1736:;
1716:64
1714:,
1704:;
1700:;
1686:MR
1684:,
1676:,
1664:28
1662:,
1652:;
1648:;
1626:;
1618:;
1614:;
1594:63
1592:,
1582:;
1567:26
1565:,
1561:,
1553:;
1513:,
1488:,
1478:;
1436:99
1434:,
1415:,
1403:46
1401:,
1391:;
1387:;
1369:43
1367:,
1346:39
1344:,
1325:,
1311:,
1290:10
1288:,
1260:,
1254:,
1231:,
1217:,
1191:35
1189:,
1179:;
1159:,
1149:;
1131:13
1129:,
1125:,
1106:28
1104:,
998:;
970:;
894:;
890:;
869:^
843:^
814:^
797:^
774:?
755:.
719:.
558:.
536:10
397:.
391:NP
378:.
358:.
273:.
197:.
121:.
1852:.
1847::
1822:.
1807:.
1797:.
1792::
1777:.
1772::
1751:6
1748:K
1729:.
1722::
1693:.
1680::
1670::
1641:.
1607:.
1600::
1575:.
1546:.
1541::
1526:.
1521::
1503:.
1496::
1471:.
1466::
1447:.
1442::
1424:.
1419::
1409::
1380:.
1375::
1357:.
1352::
1334:.
1329::
1319::
1313:5
1301:.
1296::
1275:.
1268::
1240:.
1235::
1225::
1219:6
1204:.
1197::
1172:.
1167::
1161:7
1142:.
1137::
1114:.
1096:.
1063:.
1050:.
1026:.
1002:.
986:.
974:.
958:.
946:.
934:.
922:.
898:.
864:.
838:.
809:.
705:5
702:K
698:6
695:K
691:k
683:k
679:k
667:6
664:K
656:n
645:n
641:n
606:6
603:K
571:6
568:K
556:n
552:n
548:n
544:n
540:n
533:K
529:9
526:K
508:K
504:7
501:K
333:G
325:G
268:K
261:K
250:6
247:K
233:.
211:G
137:.
119:)
117:n
115:(
113:O
79:6
76:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
