User:MWinter4/Graph embedding

This page is about embedding a graph in a general space. For how to embeddings specifically into surfaces, see Graph embedding.

In graph theory the term graph embedding (often used interchangeably with graph realization, graph representation or graph drawing) refers to a range of related ways to represent a graph geometrically. This is achieved by embedding the graph in some Euclidean space, surface, manifold or more general space. Embeddings are, despite the name, not always injective, though this might depend on the context.

Graph embeddings are the central object of study in topological and geometric graph theory.

One generally distinguished the following two types of embeddings:

• straight-line embeddings, which only describe the placement of vertices. The edges are usually assumed as straight lines between the vertices. Examples are spectral embeddings (including nullspace embeddings such as Colin de Verdière embeddings) and 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 topological embeddings include planar embeddings, book embeddings and crossing embeddings.

Examples

Straight line embeddings

• Tutte embedding
• convex embedding
• polytope skeleta
• embeddings in a force equilibrium like in Force-directed graph drawing
• frameworks in rigidity theory

Topological embeddings

In a surface

• planar embedding
• toroidal embedding

In higher dimensional space

• Linkless embedding and knotless embedding

In other spaces

• book embedding

Non-injective embeddings

• Crossing embeddings
• Spectral embedding
• Colin de Verdière embedding

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