On the area of hypercube layouts. (Q1853103)

This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. It shows that the most natural, regular layout of a hypercube of \(N^{2}\) nodes in the plane, in an \(N\times N\) grid arrangement, uses \(\lfloor2N/3\rfloor+1\) horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a full characterization of all places where the wire density is maximized (which does not occur at the bisection).