![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Heawood_graph_and_map_on_torus.png/640px-Heawood_graph_and_map_on_torus.png&w=640&q=50)
Graph embedding
Embedding a graph in a topological space, often Euclidean / From Wikipedia, the free encyclopedia
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 with vertices and simple arcs (homeomorphic images of
) are associated with edges in such a way that:
- the endpoints of the arc associated with an edge
are the points associated with 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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Heawood_graph_and_map_on_torus.png/640px-Heawood_graph_and_map_on_torus.png)
Here a surface is a connected -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. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space .[1] A planar graph is one that can be embedded in 2-dimensional Euclidean space
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".[2]
This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing" and "crossing number".