Knotless graphs edit
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 K7 and K3,3,1,1.[1] 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.[2]
One may also define graph families by the presence or absence of more complex knots and links in their embeddings,[3] or by linkless embedding in three-dimensional manifolds other than Euclidean space.[4] 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 K9 is not intrinsically triple linked, but K10 is.[5] 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.[6]
Linkless and knotless embedding edit
In two dimensions, only the planar graphs may be embedded into the Euclidean plane without crossings, but in three dimensions, any undirected graph may be embedded into space without crossings. However, a spatial analogue of the planar graphs is provided by the graphs with linkless embeddings and knotless embeddings. A linkless embedding is an embedding of the graph with the property that any two cycles are unlinked; a knotless embedding is an embedding of the graph with the property that any single cycle is unknotted. The graphs that have linkless embeddings have a forbidden graph characterization involving the Petersen family, a set of seven graphs that are intrinsically linked: no matter how they are embedded, some two cycles will be linked with each other.[7] A full characterization of the graphs with knotless embeddings is not known, but the complete graph K7 is one of the minimal forbidden graphs for knotless embedding: no matter how K7 is embedded, it will contain a cycle that forms a trefoil knot.[8]
- ^ Conway & Gordon (1983); Foisy (2002).
- ^ Foisy (2003).
- ^ Nešetřil & Thomas (1985); Fleming & Diesl (2005).
- ^ Flapan et al. (2006)
- ^ For additional examples of intrinsically triple linked graphs, see Bowlin & Foisy (2004).
- ^ Flapan et al. (2001)
- ^ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "A survey of linkless embeddings", in Robertson, Neil; Seymour, Paul (eds.), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors (PDF), Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 125–136.
- ^ Ramirez Alfonsin, J. L. (1999), "Spatial graphs and oriented matroids: the trefoil", Discrete and Computational Geometry, 22 (1): 149–158, doi:10.1007/PL00009446.