On the VLSI area and bisection width of star graphs and hierarchical cubic networks
Chi-Hsing Yeh, Behrooz Parhami · 2002
We solve an open question posed by Akers and Krishnamurthy in 1986 concerning VLSI layout of star graphs. We show that the area of the optimal layout of an N-node star graph, hierarchical cubic network (HCN), or hierarchical folded-hypercube network (HFN) is N/sup 2//16/spl plusmn/o(N/sup 2/) under the Thompson model, or under the extended grid model where a node occupies a rectangle of sides that may range from n-1 to o(/spl radic/N) for the n-star, log/sub 2/N+1 to o(/spl radic/N) for the HCN, and log/sub 2/N+2 to o(/spl radic/N) for the HFN. An n-dimensional star graph this requires less area than any possible layout of a similar-size hypercube, but more than that of the much smaller n-cube. We also derive multilayer layout for star graphs that has area N/sup 2//8[L/sup 2//2]/spl plusmn/o(N/sup 2//L/sup 2/), where a node occupies a rectangle of sides ranging from [n-1/4] to o(/spl radic/N/L) and the number L of wiring layers satisfies 2/spl les/L=o(/spl radic/N/n). Finally we show that the bisection width of an N-node star graph is N/4/spl plusmn/o(N) and the bisection width of an HCN or HFN is exactly N/4.