User:MWinter4/Knotless graph
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.