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)

Log in or register to write something here or to contact authors.