A Layout for the Shuffle-Exchange Network.

This paper describes a technique for producing a VLSI layout of the shuffle-exchange graph. It is based on the layout procedure which lays out a graph by bisecting the graph, recursively laying out the two halves, and then combining the two sublayouts. The area of the layout is related to the number of edges that must be cut to bisect the graph. For the shuffle-exchange graph on n vertices, we present a bisection schema for which the above procedure yields an On-squaredlg n area layout when n 2 to the K power and k is a power of two. The bisection involves a mapping from vertices of the graph to polynomials, and the polynomials are subsequently evaluated at complex roots of unity. Incidental to this construction is a result on the combinatorial problem of necklace enumeration. Author