Embedding grids into recursive circulants using iterative 2-edge labeling

Abstract

An important feature of an interconnection network is its ability to efficiently simulate algorithms proposed for other architectures. Such a simulation problem can be formulated as graph embedding. A good embedding is said to exist when adjacent vertices in the guest graph are mapped to reasonably close vertices in the host graph and when a path between adjacent vertices in the guest graph is chosen in a way that the congestion of the corresponding path in the host graph is moderately small. Therefore, the fitness of embedding can be measured by dilation and congestion. In this thesis, we embed grids into recursive circulant. Recursive circulant R(N, d) is a circulant graph with N vertices and jumps of power of d. We propose an embedding scheme named iterative 2-edge labeling which can embed 88.6% of grids into their optimal recursive circulant with dilation 1 and congestion 1. This algorithm also can be applied for embedding cylinder and torus into recursive circulant.