Graph embedding

In Topological graph theory, an embedding of a graph $G$ on a surface (which stands here for a compact arc-connected Hausdorff space locally homeomorphic to a disk) $\Sigma$ is the equivalence class (for homeomorphism) of representations of $G$ on $\Sigma$ in which points are associated to vertices, simple arcs (homeomorphic images of $[0;1]$) are associated to edges in such a way that:

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

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