User:MWinter4/Graph embedding

In graph theory a graph embedding (also graph realization, representation or drawing) is a way to associate to an abstract graph a geometric object. This happens by embedding the graph in some Euclidean space, surface, manifold or more general metric space. Embeddings are, despite the name, not always injective, though this might depend on the context. The two most important uses of the term graph embedding are

• vertex embeddings, which only describe the placement of vertices. The edges are usually assumed as straight lines between the vertices. Examples are spectral embeddings, nullspace embeddings, Colin de Verdière embeddings or polytope skeleta. Injectivity of the embedding is often not strictly required. Injectivity is also hard to ensure for the edges when the embedding is the result of a computational process.
• tological embeddings, which also embeds the edge as continuous curve between its end vertices and usually cares about injectivity, that is, non-crossing edges. Especially for embeddings in ${\mathbb {R}}^{3}$ the term spacial graph is used. These most often occur in topological graph theory and graph drawing.

Examples of embeddings include planar embeddings, book embeddings, topological graph embeddings and crossing embeddings.

Properties

• An embedding is linkless if no two cycles are non-trivially linked. An embedding is flat if each cycle bounds a disc whose interior is disjoint from the embedded graph. As it turns out, a graph has a linkless embedding if and only if it has a flat embedding.
• An embedding is knotless embedding if no cycle is non-trivially knotted.
• tight embedding if each hyperplane cuts the embedded graph into at most two connected components.

External links

• www.example.com