DIMENSION-ORDER ROUTING ALGORITHMS FOR A FAMILY OF MINIMAL-DIAMETER CIRCULANTS
Pranava K. Jha · Journal of Interconnection Networks · 2013
This paper presents a family of minimal-diameter, four-regular nonbipartite circulants on 2a2 vertices, where a is odd. If a ≡ 3 mod (4), then the step sizes are 1 and (a − 1)2, and if a ≡ 1 mod (4), then the step sizes are 1 and (a + 1)2. Each graph is obtainable from the 2a × a rectangular twisted torus by appropriately trading a total of 3a − 1 edges for as many new edges. Further, each admits an almost-square L-shaped embedding in the two-dimensional Cartesian plane, facilitating a plane tessellation that leads to an efficient dimension-order routing algorithm.