A COMPACT LAYOUT OF THE BUTTERFLY
Yefim Dinitz, Shimon Even, Maria Zapolotsky · Journal of Interconnection Networks · 2003
For the Butterfly of N input/output vertices we present a layout on the rectilinear (square) grid of area ½N2 + o(N2). A lower bound of the same order is proved. The encompassing rectangle which defines the area is 45° slanted w.r.t. the grid axes and the input/output vertices are not on the boundary of this rectangle. The layout is component-scalable, i.e., if one allocates for each switch a square of a × a area, the layout remains of area ½N2 + o(N2); that is, the value of a affects only the o(N2) term. The layout is also free of knock-knees.