On VLSI layouts of the star graph and related networks. (English) Zbl 0813.94026
Summary: We prove that the minimal VLSI layout of the arrangement graph \(A(n,k)\) occupies an area \(\Theta (n!/(n - k - 1 )!)^ 2\). As a special case we obtain an optimal layout for the star graph \(S_ n\) with the area \(\Theta (n!)^ 2\). This answers an open problem posed by S. B. Akers and B. Krishnamurthy [IEEE Trans. Comput. 36, 885-888 (1987; Zbl 0641.94049)]. The method is also applied to the pancake graph. The results provide optimal upper and lower bounds for crossing numbers of the above graphs.
MSC:
94C15 | Applications of graph theory to circuits and networks |
68M10 | Network design and communication in computer systems |
68W35 | Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) |
05C90 | Applications of graph theory |