Nearly Optimal Three Dimensional Layout of Hypercube Networks

Calamoneri, Tiziana and Massini, Annalisa (2004) Nearly Optimal Three Dimensional Layout of Hypercube Networks. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 247-258 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_23).

Full text not available from this repository.

Abstract

In this paper we consider the three-dimensional layout of hypercube networks. Namely, we study the problem of laying hypercube networks out on the three-dimensional grid with the properties that all nodes are represented as rectangular slices and lie on two opposite sides of the bounding box of the layout volume. We present both a lower bound and a layout method providing an upper bound on the layout volume of the hypercube network.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_23
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.060 3D
P Styles > P.999 Others
ID Code:532

Repository Staff Only: item control page

References

T. Biedl, T. Thiele, D. R. Wood: Three-Dimensional Orthogonal Graph Drawing with Optimal Volume. Proc. Graph Drawing (GD'00), pp. 284-295, 2001.

T. Calamoneri, A. Massini: An Optimal Layout of Multigrid Networks. Information Processing Letters, 72, pp. 137-141, 1999.

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

A. DeHon: Compact, Multilayer Layout for Butterfly Fat-Tree. ACM Symp. on Parallel Algorithms and Architectures (SPPA), 2000.

P. Eades, A. Symvonis, S. Whitesides: Two Algorithms for Three Dimensional Orthogonal Graph Drawing. Proc. Graph Drawing '96 (GD'96), Lecture Notes in Computer Science 1190, Springer-Verlag, 1996, pp. 139-154.

R. I. Greenberg and L. Guan: On the area of hypercube layouts. Information Processing Letters, 84, pp. 41-46, 2002.

F. T. Leighton: Introduction to Parallel Algorithms and Architecture: Arrays, Trees and Hypercubes, Morgan Kaufmann Publ., San Mateo, CA, 1992.

K. Melhorn, F. P. Preparata and M. Sarrafzadeh: Channel routing in knock-knee mode: simplified algorithms and proofs. Algorithmica 1, 213-221, 1986.

S. Muthukrishnan, M. Paterson, S. C. Sahinalp and T. Suel: Compact Grid Layouts of Multi-Level Networks. 31st ACM Symp. on Theory of Computing, 1999.

R. Y. Pinter, On routing two-point nets across a channel, 19th ACM-IEEE Design Automation Conf. (1982) 894-902.

A. L. Rosenberg: Three-Dimensional VLSI: A Case-Study. Journal of the ACM, 30(3), 1983, pp. 397-416.

D. R. Wood: A New Algorithm and Open Problems in Three-Dimensional Orthogonal Graph Drawing. Proc. 10th Australasian Work. Combinatorial Algorithms (AWOCA), pp. 157-167, 1999.

T. Yamada and S. Ueno: On Three-Dimensional Layout of De Bruijn Networks. 2002 IEEE International Symposium on Circuits and Systems (ISCAS '02), Vol. III, pp. 779-782, 2002.

T. Yamada and S. Ueno: On Three-Dimensional Layout of Pyramid Networks. 2002 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS '02), 2002.

C.-H. Yeh, B. Parhami, E. A. Varvarigos and H. Lee: VLSI Layout and Packaging of Butterfly Networks. ACM Symp. on Parallel Algorithms and Architectures (SPPA), pp. 196-205, 2000.

C.-H. Yeh, E. A. Varvarigos and B. Parhami: Multilayer VLSI Layout for Interconnection Networks. 2000 Int.l Conference on Parallel Processing (ICPP), pp. 33-40, 2002.