Linkless embeddings of graphs in space
Authors:
Neil Robertson, P. D. Seymour and Robin Thomas
Journal:
Bull. Amer. Math. Soc. 28 (1993), 8489
MSC:
Primary 57M15; Secondary 05C10
MathSciNet review:
1164063
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We announce results about flat (linkless) embeddings of graphs in 3space. A piecewiselinear embedding of a graph in 3space 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 3space 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 or . (iii) Any flat embedding of a graph can be transformed to any other flat embedding of the same graph by "3switches", an analog of 2switches from the theory of planar embeddings. In particular, any two flat embeddings of a 4connected 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 by means of  and exchanges.
 [1]
Thomas
Böhme, On spatial representations of graphs, Contemporary
methods in graph theory, Bibliographisches Inst., Mannheim, 1990,
pp. 151–167. MR 1126225
(93a:05053)
 [2]
, Lecture at the AMS Summer Research Conference on Graph Minors, Seattle, WA, June 1991.
 [3]
J.
H. Conway and C.
McA. Gordon, Knots and links in spatial graphs, J. Graph
Theory 7 (1983), no. 4, 445–453. MR 722061
(85d:57002), http://dx.doi.org/10.1002/jgt.3190070410
 [4]
Gordon
M. Fisher, On the group of all homeomorphisms of
a manifold, Trans. Amer. Math. Soc. 97 (1960), 193–212. MR 0117712
(22 #8487), http://dx.doi.org/10.1090/S00029947196001177129
 [5]
Dick
Wick Hall, A note on primitive skew
curves, Bull. Amer. Math. Soc. 49 (1943), 935–936. MR 0009442
(5,151b), http://dx.doi.org/10.1090/S000299041943080652
 [6]
C. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271283.
 [7]
W.
K. Mason, Homeomorphic continuous curves in
2space are isotopic in 3space., Trans. Amer.
Math. Soc. 142
(1969), 269–290. MR 0246276
(39 #7580), http://dx.doi.org/10.1090/S00029947196902462762
 [8]
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.
 [9]
N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, submitted.
 [10]
N. Robertson, P. D. Seymour, and R. Thomas, Kuratowski chains, submitted.
 [11]
, Petersen family minors, submitted.
 [12]
, Sachs' linkless embedding conjecture, manuscript.
 [13]
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
(85b:05077), http://dx.doi.org/10.1007/BFb0071633
 [14]
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, NorthHolland, Amsterdam, 1984,
pp. 649–662. MR 818267
(87c:05055)
 [15]
H. Saran, Constructive results in graph minors: Linkless embeddings, Ph.D. thesis, University of California at Berkeley, 1989.
 [16]
Martin
Scharlemann and Abigail
Thompson, Detecting unknotted graphs in 3space, J.
Differential Geom. 34 (1991), no. 2, 539–560.
MR
1131443 (93a:57012)
 [17]
Hassler
Whitney, 2Isomorphic Graphs, Amer. J. Math.
55 (1933), no. 14, 245–254. MR
1506961, http://dx.doi.org/10.2307/2371127
 [18]
Ying
Qing Wu, On planarity of graphs in 3manifolds, Comment. Math.
Helv. 67 (1992), no. 4, 635–647. MR 1185812
(93m:57002), http://dx.doi.org/10.1007/BF02566522
 [1]
 T. Böhme, On spatial representations of graphs, Contemporary Methods in Graph Theory (R. Bodendieck, ed.), Mannheim, Wien, Zurich, 1990, pp. 151167. MR 1126225 (93a:05053)
 [2]
 , Lecture at the AMS Summer Research Conference on Graph Minors, Seattle, WA, June 1991.
 [3]
 J. H. Conway and C. McA. Gordon, Knots and links in spatial graphs, J. Graph Theory 7 (1983), 445453. MR 722061 (85d:57002)
 [4]
 G. M. Fisher, On the group of all homeomorphisms of a manifold, Trans. Amer. Math. Soc. 97 (1960), 193212. MR 0117712 (22:8487)
 [5]
 D. W. Hall, A note on primitive skew curves, Bull. Amer. Math. Soc. 49 (1943), 935937. MR 0009442 (5:151b)
 [6]
 C. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271283.
 [7]
 W. K. Mason, Homeomorphic continuous curves in 2space are isotopic in 3space, Trans. Amer. Math. Soc. 142 (1969), 269290. MR 0246276 (39:7580)
 [8]
 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.
 [9]
 N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, submitted.
 [10]
 N. Robertson, P. D. Seymour, and R. Thomas, Kuratowski chains, submitted.
 [11]
 , Petersen family minors, submitted.
 [12]
 , Sachs' linkless embedding conjecture, manuscript.
 [13]
 H. Sachs, On spatial representation of finite graphs (Proceedings of a conference held in Lagów, February 1013, 1981, Poland), Lecture Notes in Math., vol. 1018, SpringerVerlag, Berlin, Heidelberg, New York, and Tokyo, 1983. MR 730653 (85b:05077)
 [14]
 , On spatial representations of finite graphs, finite and infinite sets, (A. Hajnal, L. Lovász, and V. T. Sós, eds), Colloq. Math. Soc. János Bolyai, vol. 37, NorthHolland, Budapest, 1984, pp. 649662. MR 818267 (87c:05055)
 [15]
 H. Saran, Constructive results in graph minors: Linkless embeddings, Ph.D. thesis, University of California at Berkeley, 1989.
 [16]
 M. Scharlemann and A. Thompson, Detecting unknotted graphs in 3space, J. Differential Geom. 34 (1991), 539560. MR 1131443 (93a:57012)
 [17]
 H. Whitney, 2isomorphic graphs, Amer. J. Math. 55 (1933), 245254. MR 1506961
 [18]
 Y.Q. Wu, On planarity of graphs in 3manifolds, Comment. Math. Helv. (to appear). MR 1185812 (93m:57002)
Similar Articles
Retrieve articles in Bulletin of the American Mathematical Society
with MSC:
57M15,
05C10
Retrieve articles in all journals
with MSC:
57M15,
05C10
Additional Information
DOI:
http://dx.doi.org/10.1090/S027309791993003355
PII:
S 02730979(1993)003355
Article copyright:
© Copyright 1993 American Mathematical Society
