Abstract: We survey the known results concerning embeddings of graphs into hypercube graphs, including a necessary and sufficient criterion for a graph to be cubical (a graph G is cubical if it can be embedded into a hypercube so that no two vertices of G are mapped onto the same vertex of the hypercube, and if two vertices are adjacent G then they are mapped to adjacent vertices in the hypercube). Other results include expansion/dilation tradeoffs for general graphs, embeddings of meshes and trees, packings of multiple copies of a graph, the NP-completeness of finding good embeddings, and critical graphs which are minimal with respect to some property. In addition, we describe several open problems.

Our motivation for looking at these embeddings came from parallel computing. One important aspect of the efficient use of a hypercube computer to solve a given problem is the assignment of subtasks to processors in such a way that the communication overhead is low. The subtasks and their inter-communication requirements can be modeled by a directed graph, and the assignment of subtasks to processors can be viewed as an embedding of the task graph into the graph of the hypercube network.

Keywords: hypercube graph, parallel computer, n-cube, embedding, dilation, expansion, cubical, packing, random graphs, critical graphs

Complete paper: In Postcript or PDF. This paper appears in Mathematical and Computational Modeling 11 (1988), pp. 222-227.

Copyright © 2005-2008 Quentin F. Stout