Graph embedding

A graph embedding maps one graph injectively into another while preserving specified structure, such as adjacency or topological connections. The exact preservation requirements depend on the embedding notion.

Graph homomorphism: A vertex map between graphs that sends every edge to an edge, but need not be injective or preserve nonedges. It preserves adjacency but lacks the injectivity required by many graph embeddings.
Graph: A mathematical structure consisting of vertices and edges connecting pairs of vertices. An embedding compares a source graph with a target graph.
Subgraph isomorphism problem: The computational problem of deciding whether one graph is isomorphic to a subgraph of another. It asks directly whether an injective adjacency-preserving embedding exists.
Metric embedding: A map between metric spaces that controls distances according to specified distortion bounds. Metric embeddings preserve distance behavior, whereas graph embeddings usually preserve combinatorial structure.
Subgraph: A graph formed from a subset of another graph’s vertices and a subset of its edges. An embedding often realizes the source as a subgraph of the target.
Injective function: A function that maps distinct elements of its domain to distinct elements of its codomain. Injectivity ensures that distinct source vertices do not collapse onto one target vertex.
Graph drawing: The placement of graph vertices and edges in a geometric space under specified visual constraints. A drawing can be viewed as embedding a graph into a plane or surface.
Minor-closed graph property: A graph property preserved when vertices or edges are deleted or edges are contracted. Minor containment is a broader structural relation than subgraph embedding.
Induced subgraph: A subgraph containing every edge of the original graph whose endpoints both lie in the selected vertex set. An induced embedding preserves both adjacency and nonadjacency among mapped vertices.
Adjacency matrix: A matrix recording which pairs of vertices in a graph are joined by edges. Matrix representations make adjacency-preservation conditions explicit.

Linked from 7 pages