Optimal layout of recursive circulant graphs

Abstract

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\ge 2,n$ even into paths (MinLA), 1-rooted complete binary trees, regular caterpillars and ladders.

Keywords:

• Embedding
• congestion lemma
• maximum subgraph
• recursive circulant

AMS CLASSIFICATION:

• 05C30

Disclosure statement

No potential conflict of interest was reported by the author(s).