Optimal layout of recursive circulant graphs

摘要

Graph is a mathematical model represented by points and lines joining certain pairs of points. These points are addressed as vertices or nodes and the lines are addressed as edges or links. Graph embedding is a mapping of guest graph G into host graph H satisfying certain conditions. Embedding has been studied for many networks in the literature. The Recursive Circulant RC(2~n,4) has several attractive topological properties. Though the embedding of parallel architectures such as Hypercubes and Mesh into Recursive Circulant has been studied, the embedding of Recursive Circulant into other architectures has not been taken up so far. In this paper, we compute the wirelength of embedding RC(2~n, 4), n ≥ 2, n even into paths (MinLA), 1 -rooted complete binary trees, regular caterpillars and ladders.