Embeddings in Hypercubes

Marilynn Livingston
Dept. of Computer Science, Southern Illinois University at Edwardsville

Quentin F. Stout
Computer Science and Engineering, University of Michigan

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.


Related Work: here are my papers in graph theory and in parallel computing. Keywords are included so that you can search for relevant papers. Especially relevant to this paper are Packings in hypercubes, Distributing Resources in Hypercube Computers and Hypercubes and pyramids.

Quentin F. Stout Home Copyright © 2005-2021 Quentin F. Stout