A General Method for Efficient Embeddings of Graphs into Optimal Hypercubes
Embeddings of several graph classes into hypercubes have been widely
studied.
Unfortunately, almost all investigated graph classes are regular graphs
such as meshes, complete trees, pyramids.
In this paper, we present a general method for one-to-one embedding
irregular graphs into their optimal hypercubes based on
extended-edge-bisectors of graphs.
An extended-edge-bisector is an edge-bisector with the additional property
that a subset of the vertices is distributed more or less evenly among the
two halves of the bisected graph.
The dilation and congestion of the embedding depends on the quality of the
extended-edge-bisector.
Moreover, if the extended bisection can be efficiently computed on the
hypercube, so can the embedding.
