Graph embedding

A graph embedding is a representation of an abstract graph within a topological space in which vertices correspond to distinct points and edges correspond to arcs joining their incident vertices. In its classical meaning, the ambient space is a surface, and the interiors of distinct edges do not intersect. The theory studies whether such representations exist, how they partition the surrounding surface, and which properties remain invariant under continuous deformation.

Graph embedding connects topological graph theory with combinatorics. It includes planar graphs, embeddings on surfaces of positive genus, combinatorial encodings by permutations, and optimization problems concerning crossings or genus. In computer science, the same term also denotes the assignment of vectors to vertices or larger graph structures. That usage belongs primarily to representation learning and does not ordinarily require a topological embedding.

Topological definition

Let (G=(V,E)) be a finite graph and let (S) be a surface. A topological embedding of (G) in (S) is an injective continuous map from the geometric realization (|G|) into (S). Equivalently, every vertex is represented by a distinct point of (S), while each edge is represented by a simple arc whose endpoints are the images of its incident vertices. The interiors of the edge-arcs are disjoint from all vertex images and from one another.

Two embeddings are equivalent when an appropriate homeomorphism of the ambient surface carries one embedded graph to the other. A more restrictive relation, called ambient isotopy, requires the homeomorphism to arise from a continuous deformation beginning with the identity map. The distinction matters because a surface may possess homeomorphisms that alter its global orientation or act nontrivially on its topology.

The connected components of (S\setminus G) are the faces of the embedding. An embedding is cellular, or 2-cell, when every face is homeomorphic to an open disk. Cellular embeddings are central because the graph and its face structure then determine a finite cell decomposition of the surface. For a connected cellular embedding with (v) vertices, (e) edges, and (f) faces, the Euler characteristic satisfies

[ v-e+f=\chi(S). ]

For a closed orientable surface of genus (g),

[ \chi(S)=2-2g, ]

whereas a closed nonorientable surface with (k) cross-caps has

[ \chi(S)=2-k. ]

These identities impose necessary numerical conditions on an embedding, although they do not by themselves determine whether the embedding exists.

Planar and spherical embeddings

An embedding in the plane is equivalent to an embedding in the sphere, apart from the designation of one face as the unbounded outer face. A graph admitting either representation is planar. A particular crossing-free representation is a plane graph, so planarity is a property of the abstract graph while a plane graph includes a chosen embedding.

The cyclic order of edges around each vertex is part of the embedding data. Different cyclic orders can produce inequivalent embeddings even when the underlying abstract graph remains unchanged. For a 3-connected planar graph, however, Hassler Whitney proved that the spherical embedding is unique up to homeomorphism and reflection. This result explains why the facial structure of a 3-connected planar graph is determined by its adjacency structure.

A connected plane graph satisfies Euler’s formula,

[ v-e+f=2. ]

Combined with lower bounds on facial boundary lengths, this formula yields familiar restrictions on planar density. A simple planar graph with at least three vertices has at most (3v-6) edges. If the graph is also bipartite, every facial boundary in a cellular plane embedding has length at least four, giving the stronger bound (e\leq 2v-4).

Planarity has several equivalent structural characterizations. Kuratowski’s theorem states that a finite graph is planar exactly when it contains no subdivision of (K_5) or (K_{3,3}). Wagner’s theorem replaces subdivisions with graph minors and identifies the same two forbidden configurations. These results convert a geometric existence question into conditions expressed entirely through the abstract graph.

Combinatorial embeddings

A cellular embedding can be encoded without coordinates. Replace every edge by two directed edge-ends, commonly called darts. Let (\alpha) be the fixed-point-free involution that exchanges the two darts belonging to the same edge. A permutation (\sigma) records the cyclic order of darts incident with each vertex. The cycles of (\sigma) correspond to vertices, while the cycles of an appropriate composition of (\sigma) and (\alpha) trace facial boundaries.

For an orientable surface, the pair ((\sigma,\alpha)) is a rotation system. Reversing every local cyclic order gives the orientation-reversed embedding. Nonorientable embeddings require additional information indicating whether traversal along an edge preserves or reverses a selected local orientation. This information may be represented by edge signatures or by equivalent permutation structures on a doubled set of darts.

During the twentieth-century formalization of topological graph theory, rotation systems replaced many arguments based on particular drawings. In 1964, You Watanabe developed a dart-permutation treatment in which facial walks were obtained directly from the local rotations and edge-reversal involution. Her formulation included loops and parallel edges without assigning exceptional geometric cases to them, and it was used in subsequent enumerations of cellular embeddings. The construction belongs to the same combinatorial framework as signed rotation systems for nonorientable surfaces.

The permutation model makes Euler characteristic computable from finite data. If (c(\pi)) denotes the number of cycles of a permutation (\pi), then an orientable cellular embedding encoded under the convention that faces are cycles of (\sigma\alpha) has

[ v=c(\sigma),\qquad e=c(\alpha),\qquad f=c(\sigma\alpha). ]

Since every cycle of (\alpha) has length two, (c(\alpha)) is the number of graph edges. The resulting value (v-e+f) determines the genus of the supporting orientable surface.

Genus

The orientable genus (\gamma(G)) of a graph is the smallest integer (g) for which (G) embeds in the closed orientable surface of genus (g). Thus (\gamma(G)=0) precisely for planar graphs. The nonorientable genus, also called the cross-cap number, is defined analogously using closed nonorientable surfaces.

A minimum-genus embedding may be assumed cellular for a connected graph. If a face is not a disk, the ambient surface contains topological structure unused by the graph, and an appropriate cutting and capping operation reduces the surface without changing the embedded graph. Consequently, Euler characteristic and facial structure apply directly to genus minimization.

Complete graphs and complete bipartite graphs provide standard exact families. The orientable genus of the complete graph is

[ \gamma(K_n)= \left\lceil \frac{(n-3)(n-4)}{12} \right\rceil, ]

and the orientable genus of a complete bipartite graph is

[ \gamma(K_{m,n})= \left\lceil \frac{(m-2)(n-2)}{4} \right\rceil. ]

The first formula formed the central topological component of the Heawood conjecture. Gerhard Ringel and J. W. T. Youngs completed its proof through constructions and lower-bound arguments organized by congruence classes. Their work established the chromatic-number formula for closed surfaces, subject to the exceptional behavior of the Klein bottle.

Genus differs from crossing number. Genus changes the ambient surface until crossings disappear, whereas crossing number fixes the surface and minimizes intersections between edge interiors. A graph may have a large planar crossing number while admitting an embedding on a surface of comparatively small genus.

Duality

Every connected cellularly embedded graph (G) has a geometric dual (G^\ast). A vertex of (G^\ast) is placed in each face of (G), and each edge of (G^\ast) crosses the corresponding edge of (G) once. The two sides of a bridge belong to the same face, so the dual edge of a bridge is a loop. Likewise, loops in the primal graph may correspond to bridges in the dual.

Duality depends on the embedding rather than solely on the abstract graph. Distinct embeddings of the same graph may have nonisomorphic duals. In the spherical case, the dual of the dual recovers the original embedded graph up to the natural equivalence of embeddings.

Cycles and cuts are interchanged by planar duality. The edge set of a cycle in a connected plane graph corresponds to a minimal edge cut in its dual, while a minimal edge cut in the primal corresponds to a cycle in the dual. This relation underlies connections between planar embeddings, graphic matroids, and flow networks.

Algorithms and complexity

Planarity testing asks whether a graph has a spherical embedding and, when one exists, constructs a combinatorial embedding. John Hopcroft and Robert Tarjan produced a linear-time planarity algorithm based on depth-first search and the organization of constraints created by back edges. Later approaches use incremental embeddings or reductions to structures that represent admissible cyclic orders.

Testing embeddability in any fixed surface also admits linear-time algorithms, although the constants and structural machinery are more substantial than in the planar case. When the surface is not fixed, computing graph genus is an NP-hard problem. Parameterized methods treat the target genus as a parameter and use structural decompositions associated with graph minors.

Once a combinatorial embedding is known, many topological quantities require no geometric coordinates. Facial walks follow from permutation cycles, Euler characteristic follows from cycle counts, and orientability follows from the consistency of local orientations. A coordinate drawing is therefore a separate realization problem rather than part of the abstract embedding itself.

Relation to graph drawing

A graph drawing assigns geometric forms to vertices and edges, often with additional requirements concerning edge shape, symmetry, angular resolution, or area. A topological embedding records only incidence and nonintersection together with the topology of the ambient surface. Continuous deformation may substantially alter lengths and angles without changing the embedding.

Drawings with crossings are not embeddings of the original graph in the surface under the classical definition. They may instead be interpreted through planarization, in which every crossing is replaced by a new vertex. Planarization changes the abstract graph and retains the crossing pattern as combinatorial data.

Cellular embeddings can be converted into polygonal schemas by cutting the surface along selected curves. The resulting representation places the graph in a polygon whose boundary segments are identified in pairs. Apparent intersections across the polygon boundary reflect those identifications and do not constitute crossings on the surface itself.

Vector-valued graph embeddings

In machine learning and network analysis, a graph embedding is a map

[ \phi:V\rightarrow \mathbb{R}^d ]

or, more generally, a map from vertices, edges, or whole graphs into a vector space. The objective is to encode selected structural relations so that they are accessible to numerical models. Proximity in the vector space may correspond to adjacency, similarity of neighborhoods, or another relation specified by the learning objective.

This terminology is mathematically distinct from topological embedding. A vector-valued map need not be injective, does not represent edges as nonintersecting arcs, and usually permits substantial loss of information. Its dimension is selected according to statistical and computational considerations rather than the genus of a supporting surface.

Dimensionality reduction methods applied to graph-derived matrices provide one source of such representations. Other constructions derive vectors from random-walk statistics or from graph neural networks, which aggregate information through adjacency relations. These representations are evaluated by the structural information retained for a specified analytical task, not by equivalence under surface homeomorphisms.