New layouts for the shuffle-exchange graph(Extended Abstract)
Daniel J. Kleitman, Frank Thomson Leighton, Margaret A. Lepley, Gary Lee Miller · 1981
In this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n2/log2n) area. The optimal layout is described and analyzed in section 3. The analysis is heavily dependent on several combinatorial results which we state in section 2 and prove in the appendix. The other layouts are described in section 4. Although these layouts are not asymptotically optimal (most require 0(n2/log3/2n) area), the theory behind their development is interesting and may eventually lead to good practical layouts as well as other asymptotically optimal layouts.