Embedding a graph in 3D space with no cycles interlinked
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.[1] Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.
Flat embeddings are automatically linkless, but not vice versa.[2] The complete graph K6, the Petersen graph, and the other five graphs in the Petersen family do not have linkless embeddings.[1] Every graph minor of a linklessly embeddable graph is again linklessly embeddable,[3] as is every graph that can be reached from a linklessly embeddable graph by YΔ- and ΔY-transformations.[2] The linklessly embeddable graphs have the Petersen family graphs as their forbidden minors,[4] and include the planar graphs and apex graphs.[2] They may be recognized, and a flat embedding may be constructed for them, in O(n2).[5]
^ abSachs (1983).
^ abcCite error: The named reference rst93a was invoked but never defined (see the help page).
^Cite error: The named reference nt85 was invoked but never defined (see the help page).
^Robertson, Seymour & Thomas (1995).
^Cite error: The named reference kkm10 was invoked but never defined (see the help page).
and 15 Related for: Linkless embedding information
topological graph theory, a mathematical discipline, a linklessembedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean...
embedding, cellular embedding or map is an embedding in which every face is homeomorphic to an open disk. A closed 2-cell embedding is an embedding in...
planar graph. A 1-outerplanar embedding of a graph is the same as an outerplanar embedding. For k > 1 a planar embedding is k-outerplanar if removing the...
minors and play a role in several other aspects of graph minor theory: linklessembedding, Hadwiger's conjecture, YΔY-reducible graphs, and relations between...
algebraic analogs for the Milnor invariants. A linklessembedding of an undirected graph is an embedding into three-dimensional space such that every two...
family. These graphs form the forbidden minors for linklesslyembeddable graphs, graphs that can be embedded into three-dimensional space in such a way that...
theorem Khovanov homology Knot group Knot tabulation Knotless embeddingLinklessembedding Link concordance Link group Link (knot theory) Milnor conjecture...
one of the forbidden minors for linklessembedding. In other words, and as Conway and Gordon proved, every embedding of K6 into three-dimensional space...
Holst, Hein (March 2009), "A polynomial-time algorithm to find a linklessembedding of a graph", Journal of Combinatorial Theory, Series B, 99 (2), Elsevier...
S2CID 209133. Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linklessembeddings of graphs in 3-space", Bulletin of the American Mathematical Society...
These seven graphs form the forbidden minors for linklesslyembeddable graphs, graphs that can be embedded into three-dimensional space in such a way that...
outerplanarity. A 1-outerplanar embedding of a graph is the same as an outerplanar embedding. For k > 1 a planar embedding is said to be k-outerplanar if...
the existence of a polynomial-time algorithm for problems such as linklessembedding without allowing the algorithm itself to be explicitly constructed;...
with Hadwiger number at most five include the apex graphs and the linklesslyembeddable graphs, both of which have the complete graph K6 among their forbidden...
computational complexity as testing whether an embedding of an undirected graph in Euclidean space is linkless. Several algorithms solving the unknotting...
Global Information