In topological graph theory, an embedding (also spelled imbedding) of a graph ${\displaystyle G}$ on a surface ${\displaystyle \Sigma }$ is a representation of ${\displaystyle G}$ on ${\displaystyle \Sigma }$ in which points of ${\displaystyle \Sigma }$ are associated with vertices and simple arcs (homeomorphic images of ${\displaystyle [0,1]}$) are associated with edges in such a way that:

Here a surface is a connected ${\displaystyle 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. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space ${\displaystyle \mathbb {R} ^{3}}$. A planar graph is one that can be embedded in 2-dimensional Euclidean space ${\displaystyle \mathbb {R} ^{2}.}$

Often, an embedding is regarded as an equivalence class (under homeomorphisms of ${\displaystyle \Sigma }$) 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".

If a graph ${\displaystyle G}$ is embedded on a closed surface ${\displaystyle \Sigma }$, the complement of the union of the points and arcs associated with the vertices and edges of ${\displaystyle G}$ is a family of regions (or faces). A 2-cell embedding, cellular embedding or map is an embedding in which every face is homeomorphic to an open disk. A closed 2-cell embedding is an embedding in which the closure of every face is homeomorphic to a closed disk.

The genus of a graph is the minimal integer ${\displaystyle n}$ such that the graph can be embedded in a surface of genus ${\displaystyle n}$. In particular, a planar graph has genus ${\displaystyle 0}$, because it can be drawn on a sphere without self-crossing. A graph that can be embedded on a torus is called a toroidal graph.