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 [0,1]} ) are associated with edges in such a way that:
the endpoints of the arc associated with an edge e {\displaystyle e} are the points associated with the end vertices of e , {\displaystyle e,}
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 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}} . A planar graph is one that 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".
Terminology 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 with the 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. The genus of a graph is the minimal integer n {\displaystyle n} such that the graph can be embedded in a surface of genus n {\displaystyle n} . In particular, a planar graph has genus 0 {\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. The non-orientable genus of a graph is the minimal integer n {\displaystyle n} such that the graph can be embedded in a non-orientable surface of (non-orientable) genus n {\displaystyle n} . The Euler genus of a graph is the minimal integer n {\displaystyle n} such that the graph can be embedded in an orientable surface of (orientable) genus n / 2 {\displaystyle n/2} or in a non-orientable surface of (non-orientable) genus n {\displaystyle n} . A graph is orientably simple if its Euler genus is smaller than its non-orientable genus. The maximum genus of a graph is the maximal integer n {\displaystyle n} such that the graph can be 2 {\displaystyle 2} -cell embedded in an orientable surface of genus n {\displaystyle n} .
Combinatorial embedding
An embedded graph uniquely defines cyclic orders of edges incident to the same vertex. The set of all these cyclic orders is called a rotation system. Embeddings with the same rotation system are considered to be equivalent and the corresponding equivalence class of embeddings is called combinatorial embedding (as opposed to the term topological embedding, which refers to the previous definition in terms of points and curves). Sometimes, the rotation system itself is called a "combinatorial embedding". An embedded graph also defines natural cyclic orders of edges which constitutes the boundaries of the faces of the embedding. However handling these face-based orders is less straightforward, since in some cases some edges may be traversed twice along a face boundary. For example this is always the case for embeddings of trees, which have a single face. To overcome this combinatorial nuisance, one may consider that every edge is "split" lengthwise in two "half-edges", or "sides". Under this convention in all face boundary traversals each half-edge is traversed only once and the two half-edges of the same edge are always traversed in opposite directions. Other equivalent representations for cellular embeddings include the ribbon graph, a topological space formed by gluing together topological disks for the vertices and edges of an embedded graph, and the graph-encoded map, an edge-colored cubic graph with four vertices for each edge of the embedded graph.
… excerpt ends here. Continue reading the full article.
