Graph embedding

In <a href="/facts/Topological_graph_theory/TAQ2DdVB">topological graph theory</a>, an embedding (also spelled imbedding) of a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> 
 
 
 
 G
 
 
 {\displaystyle G}
 
 on a <a href="/facts/Surface_(mathematics)/whF08jvy">surface</a> 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
 is a representation of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 on 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
 in which points of 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
 are associated with <a href="/facts/Graph_theory/VVPCd4TX">vertices</a> and simple arcs (<a href="/facts/Homeomorphism/jMfWg3Mn">homeomorphic</a> images of 
 
 
 
 [
 0
 ,
 1
 ]
 
 
 {\displaystyle [0,1]}
 
) are associated with <a href="/facts/Graph_theory/VVPCd4TX">edges</a> in such a way that:

<ul><li>the endpoints of the arc associated with an edge 
 
 
 
 e
 
 
 {\displaystyle e}
 
 are the points associated with the end vertices of 
 
 
 
 e
 ,
 
 
 {\displaystyle e,}
 
</li>
<li>no arcs include points associated with other vertices,</li>
<li>two arcs never intersect at a point which is interior to either of the arcs.</li></ul>
Here a surface is a <a href="/facts/Connected_space/5CUTxfoA">connected</a> 
 
 
 
 2
 
 
 {\displaystyle 2}
 
-<a href="/facts/Manifold/rXPERJtu">manifold</a>.
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 <a href="/facts/Planar_graph/plREagr9">planar graph</a> 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 "<a href="/facts/Graph_drawing/uhh73BVo">graph drawing</a>" and "<a href="/facts/Crossing_number_(graph_theory)/x3Yz6UhF">crossing number</a>".

Graph embedding open-in-new

Graph embedding