Sometimes also called Mapping, graph embedding is: given
a guest graph G_{1}(V_{1},E_{1}) and a host
graph G_{2}(V_{2},E_{2}), a graph embedding is a mapping
of each vertex in V_{1} into some vertex
in V_{2} , and a mapping of every edge in G_{1}
to a path in G_{2} that connects the mapped
vertices. The problem is to minimize load
(number of guest vertices embedded in a vertex in the host graph), dilation (the longest path that is mapped from an edge in the guest graph), and
congestion (the number of mapped paths that goes through an edge of the host graph) of the embedding. Like many interesting problems, the general graph embedding problem is NP-complete.

However, optimal embeddings for certain families of graphs (such as embedding grids into hypercubes, and vice versa) have been found. Graph embedding has applications in parallel computer architecture.

A simple subset of graph embedding, Graph Bisection, is also NP-complete. (proof)