Graph Embedding¶
A crossing-free placement of a graph's vertices and edge arcs on a specified topological surface that preserves their incidences.
Core Idea¶
A topological graph embedding places each graph vertex at a distinct point of a surface and each edge along an arc joining its endpoint points. Edge interiors neither cross each other nor pass through unrelated vertices. The mapping preserves exactly the graph's incidence. It is not simply an attractive drawing, nor the machine-learning sense of assigning vectors to graph nodes.[^ref-fc37ca639aef]
The frozen candidate came from a requested Graph genus identifier that redirected to Graph embedding. Genus is the minimum orientable surface genus on which a graph embeds, not an alias for an individual embedding. That identifier difference remains unresolved rather than being collapsed into this entry.[^ref-fc37ca639aef]
Scope of Application¶
On the sphere or plane, a graph that admits such a placement is planar. The same rule applies to a torus and other surfaces, but a graph may need a host with more topological capacity. A \(K_4\) drawing with one vertex inside an outer triangle gives a crossing-free sphere embedding. The authored mathematical chapter depicts a triangular cellular embedding of \(K_7\) on a torus, although \(K_7\) cannot embed on a sphere.[^ref-fc37ca639aef]
Faces are the complement regions. When they are all disk-like on a closed surface, the embedding is cellular and the surface Euler equation applies: \(V-E+F=2-2g\) for orientable genus \(g\). Not every embedding has this extra property, so the equation must not be applied merely because a graph was drawn.[ref-fc37ca639aef][ref-a1efbb853038]
Clarity¶
Keep the graph, chosen host and particular placement separate. A planar test asks whether a placement exists; genus minimizes over possible hosts; the embedding is the vertex-and-edge placement itself. A crossing in a flat picture might represent a genuine forbidden edge meeting, or it might only be an artifact of depicting a torus as a polygon with identified sides. Test the arcs on the stated surface.[^ref-fc37ca639aef]
Manages Complexity¶
The embedding replaces a complicated picture with a few exact conditions: distinct vertex images, endpoint-faithful arcs and no unintended meetings. For suitable cellular embeddings, faces and cyclic edge orders make the continuous placement amenable to finite combinatorial reasoning. Mohar's original algorithm paper uses rotation and signature information in that restricted setting; such data do not erase the need to check surface and cellularity assumptions.[ref-fc37ca639aef][ref-a1efbb853038]
Abstract Reasoning¶
Given a claimed embedding, verify every vertex and edge mapping and check all edge interiors for extra intersections. Then determine whether the complement faces are disk-like before using Euler counting. A sphere embedding of a connected simple graph with at least three vertices obeys \(E\leq3V-6\); \(K_7\) violates that bound with \(V=7\) and \(E=21\). On a torus its 14 triangular faces satisfy \(7-21+14=0\), consistent with orientable genus one.[^ref-fc37ca639aef]
Knowledge Transfer¶
The same exact mapping rule covers a small spherical graph and a dense toroidal one; host topology, rather than the definition of embedding, changes. The live prime Embedding is the proposed strict parent because this is a faithful injective placement with graph incidence as the preserved structure. Vector-space graph representations may share the broad parent idea but need not satisfy this entry's edge-arc and no-crossing conditions.[^ref-fc37ca639aef]
[^ref-fc37ca639aef]: Lowell W. Beineke and Robin J. Wilson, “Introduction,” in Topics in Topological Graph Theory, Cambridge University Press (2009), §§2–4, especially printed pp.10–15. [^ref-a1efbb853038]: Bojan Mohar, “Embedding Graphs in an Arbitrary Surface in Linear Time”, original 1996 ACM paper, preliminaries.
Relationships to Other Abstractions¶
Current abstraction Graph Embedding Domain-specific
Parents (1) — more general patterns this builds on
-
Graph Embedding is a kind of Embedding Prime
A graph-on-surface embedding is a faithful injective placement with graph incidence as its preserved structure.
Hierarchy path (1) — routes to 1 parentless root
- Graph Embedding → Embedding → Representation → Abstraction
Neighborhood in Abstraction Space¶
Graph Embedding sits in a moderately populated region (59th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Edge Coloring — 0.87
- Force-Directed Graph Drawing — 0.85
- Hadwiger number — 0.85
- Graph Toughness — 0.85
- Polygon — 0.84
Computed from structural-signature embeddings · 2026-10-08