Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Linkless embedding
Résumé
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. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.
Flat embeddings are automatically linkless, but not vice versa. The complete graph K_6, the Petersen graph, and the other five graphs in the Petersen family do not have linkless embeddings. Every graph minor of a linklessly embeddable graph is again linklessly embeddable, as is every graph that can be reached from a linklessly embeddable graph by a Y-Δ transform. The linklessly embeddable graphs have the Petersen family graphs as their forbidden minors, and include the planar graphs and apex graphs. They may be recognized, and a flat embedding may be constructed for them, in O(n^2).
When the circle is mapped to three-dimensional Euclidean space by an injective function (a continuous function that does not map two different points of the circle to the same point of space), its image is a closed curve.
Two disjoint closed curves that both lie on the same plane are unlinked, and more generally a pair of disjoint closed curves is said to be unlinked when there is a continuous deformation of space that moves them both onto the same plane, without either curve passing through the other or through itself. If there is no such continuous motion, the two curves are said to be linked. For example, the Hopf link is formed by two circles that each pass through the disk spanned by the other. It forms the simplest example of a pair of linked curves, but it is possible for curves to be linked in other more complicated ways.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.