Graph embedding

In topological graph theory, an embedding (also spelled imbedding) of a graph G {displaystyle G} on a surface Σ {displaystyle Sigma } is a representation of G {displaystyle G} on Σ {displaystyle Sigma } in which points of Σ {displaystyle Sigma } are associated with vertices and simple arcs (homeomorphic images of [ 0 , 1 ] {displaystyle } ) are associated with edges in such a way that: Here a surface is a compact, connected 2 {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 R 3 {displaystyle mathbb {R} ^{3}} and planar graphs can be embedded in 2-dimensional Euclidean space R 2 . {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 G {displaystyle G} is embedded on a closed surface Σ {displaystyle Sigma } , the complement of the union of the points and arcs associated withthe vertices and edges of G {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.