Graph embedding into recursively-structured graphs and hypermeshes

Abstract

Graph embedding is one of the key conceptual tools for implementing parallel algorithms or simulating interconnection networks on a parallel computer. In this thesis, we study on embeddings of graphs into a hypercube, recursive circulant, and hypermesh. First, we propose a many-to-one embedding strategy of a tree-related graph into a recursively-structured graph. Here, the tree related graph is a complete binary tree, mesh of trees or pyramid. The strategy evenly distributes the same level nodes of a tree-related graph to the nodes of the recursively-structured graph. From this strategy, we design embedding methods of a tree-related graph into a hypercube or recursive circulant. The methods are optimal or nearly optimal in terms of the general embedding measures such as dilation, congestion, and load. Second, we present one-to-one embedding methods of graphs into a hypermesh. All these embeddings are optimal in terms of alignment cost. The alignment cost is one of the important embedding measures for hypermesh. We show how to embed a butterfly using the concept of quotient group. We also show how to embed multiple copies of a graph using a labeling scheme. This embedding of multiple copies is optimal in all respects of congestion, expansion, and alignment cost. Our new or improved embedding results shows that the recursive circulant and hypermesh as well as the hypercube are versatile interconnection networks.