Graph Embedding

Graph Embedding

In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface Σ is a representation of on Σ in which points of Σ are associated to vertices and simple arcs (homeomorphic images of ) are associated to edges in such a way that:

• the endpoints of the arc associated to an edge are the points associated to the end vertices of ,
• no arcs include points associated with other vertices,
• two arcs never intersect at a point which is interior to either of the arcs.

Here a surface is a compact, connected 2-manifold.

Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints.

Often, an embedding is regarded as an equivalence class (under homeomorphisms of Σ) of representations of the kind just described.

Some authors define a weaker version of the definition of "graph embedding" by omitting the non-intersection condition for edges. In such contexts the stricter definition is described as "non-crossing graph embedding".

This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing" and "crossing number".