A tight layout of the butterfly network
Aythan Avior, Tiziana Calamoneri, Shimon Even, Ami Litman, Arnold L. Rosenberg · 1996
We establish upper and lower bounds on the layout area of the butterfly network, which differ only in low-order terms. Specifically, the N-input, N-output butterfly network can be laid out in area (1 + o(1)) N^2, while no layout of the network can have area smaller than (1 - o(1)) N^2. These results improve both the known upper bound and the known lower bound on the area of butterfly network layouts.