Linkless embeddings of graphs in $3$-space
HTML articles powered by AMS MathViewer
- by Neil Robertson, P. D. Seymour and Robin Thomas PDF
- Bull. Amer. Math. Soc. 28 (1993), 84-89 Request permission
Abstract:
We announce results about flat (linkless) embeddings of graphs in 3-space. A piecewise-linear embedding of a graph in 3-space is called flat if every circuit of the graph bounds a disk disjoint from the rest of the graph. We have shown: (i) An embedding is flat if and only if the fundamental group of the complement in 3-space of the embedding of every subgraph is free. (ii) If two flat embeddings of the same graph are not ambient isotopic, then they differ on a subdivision of ${K_5}$ or ${K_{3,3}}$. (iii) Any flat embedding of a graph can be transformed to any other flat embedding of the same graph by "3-switches", an analog of 2-switches from the theory of planar embeddings. In particular, any two flat embeddings of a 4-connected graph are either ambient isotopic, or one is ambient isotopic to a mirror image of the other. (iv) A graph has a flat embedding if and only if it has no minor isomorphic to one of seven specified graphs. These are the graphs that can be obtained from ${K_6}$ by means of $Y \Delta$- and $\Delta Y$-exchanges.References
- Thomas Böhme, On spatial representations of graphs, Contemporary methods in graph theory, Bibliographisches Inst., Mannheim, 1990, pp. 151–167. MR 1126225 —, Lecture at the AMS Summer Research Conference on Graph Minors, Seattle, WA, June 1991.
- J. H. Conway and C. McA. Gordon, Knots and links in spatial graphs, J. Graph Theory 7 (1983), no. 4, 445–453. MR 722061, DOI 10.1002/jgt.3190070410
- Gordon M. Fisher, On the group of all homeomorphisms of a manifold, Trans. Amer. Math. Soc. 97 (1960), 193–212. MR 117712, DOI 10.1090/S0002-9947-1960-0117712-9
- Dick Wick Hall, A note on primitive skew curves, Bull. Amer. Math. Soc. 49 (1943), 935–936. MR 9442, DOI 10.1090/S0002-9904-1943-08065-2 C. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271-283.
- W. K. Mason, Homeomorphic continuous curves in $2$-space are isotopic in $3$-space, Trans. Amer. Math. Soc. 142 (1969), 269–290. MR 246276, DOI 10.1090/S0002-9947-1969-0246276-2 R. Motwani, A. Raghunathan, and H. Saran, Constructive results from graph minors: Linkless embeddings, Proc. 29th Symposium on the Foundations of Computer Science, Yorktown Heights, 1988. N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, submitted. N. Robertson, P. D. Seymour, and R. Thomas, Kuratowski chains, submitted. —, Petersen family minors, submitted. —, Sachs’ linkless embedding conjecture, manuscript.
- Horst Sachs, On a spatial analogue of Kuratowski’s theorem on planar graphs—an open problem, Graph theory (Łagów, 1981) Lecture Notes in Math., vol. 1018, Springer, Berlin, 1983, pp. 230–241. MR 730653, DOI 10.1007/BFb0071633
- H. Sachs, On spatial representations of finite graphs, Finite and infinite sets, Vol. I, II (Eger, 1981) Colloq. Math. Soc. János Bolyai, vol. 37, North-Holland, Amsterdam, 1984, pp. 649–662. MR 818267 H. Saran, Constructive results in graph minors: Linkless embeddings, Ph.D. thesis, University of California at Berkeley, 1989.
- Martin Scharlemann and Abigail Thompson, Detecting unknotted graphs in $3$-space, J. Differential Geom. 34 (1991), no. 2, 539–560. MR 1131443
- Hassler Whitney, 2-Isomorphic Graphs, Amer. J. Math. 55 (1933), no. 1-4, 245–254. MR 1506961, DOI 10.2307/2371127
- Ying Qing Wu, On planarity of graphs in $3$-manifolds, Comment. Math. Helv. 67 (1992), no. 4, 635–647. MR 1185812, DOI 10.1007/BF02566522
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 28 (1993), 84-89
- MSC: Primary 57M15; Secondary 05C10
- DOI: https://doi.org/10.1090/S0273-0979-1993-00335-5
- MathSciNet review: 1164063