Sometimes also called Mapping, graph embedding is: given
a guest graph G1(V1,E1) and a host
graph G2(V2,E2), a graph embedding is a mapping
of each vertex in V1 into some vertex
in V2 , and a mapping of every edge in G1
to a path in G2 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)