Layout Volumes of the Hypercube

Torok, Lubomir and Vrt'o, Imrich (2004) Layout Volumes of the Hypercube. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 414-424 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_42).

Full text not available from this repository.

Abstract

We study 3-dimensional layouts of the hypercube in a 1-active layer and a general model. The problem can be understood as a graph drawing problem in 3D space and was addressed at Graph Drawing 2003 [5]. For both models we prove general lower bounds which relate volumes of layouts to a graph parameter called cutwidth. Then we propose tight bounds on volumes of layouts of N-vertex hypercubes. Especially, we have $ {\rm VOL}_{1-AL}(Q_{\log N})= \frac{2}{3}N^{\frac{3}{2}}\log N +O(N^{\frac{3}{2}}), $ for even log N and ${\rm VOL}(Q_{\log N})=\frac{2\sqrt{6}}{9}N^{\frac{3}{2}}+O(N^{4/3}\log N),$ for log N divisible by 3. The 1-active layer layout can be easily extended to a 2-active layer (bottom and top) layout which improves a result from [5]. This research was partially supported by the VEGA grant No. 2/3164/23.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_42
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:612

Repository Staff Only: item control page

References

Bel Hala, A., Congestion optimale du plongement de l'hybercube H(n) dans la chaine P(2n), ITA 27 (1993), 465-481.

Bezrukov, S., Chavez, J.D., Harper, L.H., Röttger, M., Schroeder, U.-P., The congestion of n-cube layout on a rectangular grid, Discrete Mathematics, 213, (2000), 13-19.

Brebner, G., Relating routing graphs and two-dimensional grids, in: Proc. VLSI: Algorithms and Architectures, North Holland, 1985.

Biedl, T., Thiele, T., Wood, D.R., Three-dimensional orthogonal graph drawing with optimal volume, in: Proc. 11th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 1984, Springer, Berlin, 2000, 284-295.

Calamoneri, T., Massini, A., Nearly optimal three-dimensional layout of hypercube networks, in: Proc. 11th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 2912, Springer, 2003, 247-258.

Calamoneri, T., Massini, A., Optimal three-dimensional layout of interconnection networks, Theoretical Computer Science 255 (2001), 263-279.

Chi-Hsiang Yeh, Varvarigos, E.A., Parhami, B., Multilayer VLSI layout for interconnection networks, in: Proc. Intl. Conf. on Parallel Processing, 2000, 21-24.

Chi-Hsiang Yeh, Varvarigos, E.A., Parhami, B., Efficient VLSI Layouts of hypercubic networks, in: Proc. Frontiers of Massivelly Parallel Computation, 1999, 98-105.

Eades, P., Symvonis, A., Whitesides, S., Two algorithms for three-dimensional graph drawing, in: Proc. 4th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 1190, Springer Berlin 1996, 139-154.

Even, S., Kupershtok, R., Layout area of the hypercube, Journal of Interconnection Networks 4 (2003), 395-417.

Greenberg, R.I., Lee Guan, On the area of hypercube networks, Information Processing Letters 41 (2002), 41-46.

Leighton, F.T., Rosenberg, A.L., Three-dimensional circuit layouts, SIAM Journal on Computing 15 (1986), 793-813.

Leiserson, C.E., Area-efficient graph layouts (for VLSI), in: Proc. 21st Annual IEEE Symposium on Foundation of Computer Science, IEEE Computer Science Press, 1980,270-281.

Patel, A., Kusalik, A, McCroskey, C., Area-efficient layouts for binary hypercubes, IEEE Transactions on Computers 49 (2000), 160-169.

Preparata, F. P., Optimal three-dimensional VLSI layouts, Mathematical Systems Theory 16 (1983), 1-8.

Raspaud, A., Sýkora, O., Vrt'o, I., Cudwidth of the de Bruijn graphs, RAIRO 26 (1995), 509-514.

Rosenberg, A.L., Three-dimensional VLSI: A case study, Journal of the ACM 30 (1983), 397-416.

Thompson, C.D., Area-time complexity for VLSI, in: Proc. 11th Annual ACM Symposium on Theory of Computing, 1979, 81-88.

Ullman, J.D., Computational Aspects of VLSI, Comp. Sci. Press, Rockville, 1983.