Abstract: We survey results concerning embeddings of graphs into hypercube graphs. A graph G is cubical if it is isomorphic to a subgraph of a hypercube, i.e., if there is a dimension d > 0 such that G can be embedded into a d-dimensional hypercube so that no two vertices of G are mapped onto the same vertex of the hypercube, and if two vertices are adjacent in G then they are mapped to adjacent vertices in the hypercube. Havel and Moravek gave a simple necessary and sufficient condition for a graph to be cubical, from which one can easily show that trees and meshes are cubical. We give expansion/dilation tradeoffs for general graphs, 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. Some of these results have not been published previously. We also give several open problems.

Our motivation for looking at these embeddings comes from parallel computing. An 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, cubical, parallel computer interconnection network, n-cube, graph embedding, dilation, expansion, packing, random graphs, critical graphs, Gray code

Complete paper. This paper appears in Mathematical and Computer Modelling 11 (1988), pp. 222-227.

Copyright © 2005-2021 Quentin F. Stout