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, specifically topological and geometric graph theory, the term graph embedding (also graph realization, graph representation or graph drawing) can refer to a number of different ways to represent a graph geometrically. This is achieved by embedding the graph in an ambient space, usually a Euclidean space, a surface, or a higher-dimensional manifold, but other more general spaces are possible as well. Depending on the context a graph embedding is assumed to be injective, where vertices are mapped to distinct points and edges do not cross; or it might allow for such intersections and double-points.

One distinguished the following two broad types of embeddings:

• straight-line embeddings only prescribe the placement of vertices; the edges are assumed as straight lines between the vertices. Examples are spectral embeddings (including nullspace embeddings such as Colin de Verdière embeddings) and polytope skeleta.
• tological embeddings embed edges as continuous curves between their end vertices. Especially for embeddings into ${\mathbb {R}}^{3}$ or the 3-sphere the term spacial graph is used. Those most often occur in topological graph theory and graph drawing. Examples of topological embeddings include planar embeddings, book embeddings and crossing embeddings.

The field of graph drawing is concerned with constructing graph embeddings specifically for the purpose of visualization. Graph embeddings in the sense of this article are mainly for theoretical considerations.

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

Related notions

• 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.
• Genus of a graph embedding is the lowest possible genus of a surface in which the graph can be embedded.

External links

• www.example.com