VLSI layout of trees into grids of minimum width

ABSTRACT

In this paper we consider the VLSI layout (i.e., Manhattan layout) of graphs into grids with minimum width (i.e., the length of the shorter side of a grid)as well as with minimum area. The layouts into minimum area and minimum width are equivalent to those with the largest possible aspect ratio of a minimum area layout. Thus such a layout has merits that, by "folding" the layout, a layout of all possible aspect ratio can be obtained with increase of area within a small constant factor. We show that an N-vertex tree with layout-width (i.e., the minimum width of a grid into which the tree can be laid out) k can be laid out into a grid of area O(N) and width O(k). For binary tree layouts, we give a detailed trade-off between area and width: an N-vertex binary tree with layout-width k can be laid out into area O(k+α/1+αN) and width k+α, where α is an arbitrary integer with 0≤ α≤√N, and the area is existentially optimal for any k≥ 1 and α≥ 0. This implies that α=ω(k) is essential for a layout of a graph into optimal area. The layouts proposed here can be constructed in polynomial time. We also show that the problem of laying out a given graph G into given area and width, or equivalently, into given length and width is NP-hard even if G is restricted to a binary tree.

REFERENCES

• 1: Sandeep N. Bhatt , Stavros S. Cosmadakis, The complexity of minimizing wire lengths in VLSI layouts, Information Processing Letters, v.25 n.4, p.263-267, June 17, 1987 [doi>10.1016/0020-0190(87)90173-6]
• 2: S. N. Bhatt and F. T. Leighton. A framework for solving VLSI graph layout problems. J. Comput. System Sciences, 28:300--343, 1984.
• 3: Timothy M. Chan , Michael T. Goodrich , S. Rao Kosaraju , Roberto Tamassia, Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings, Proceedings of the Symposium on Graph Drawing, p.63-75, September 18-20, 1996
• 4: P. Czerwinski and V. Ramachandran. Optimal VLSI graph embeddings in variable aspect ratio rectangles. Algorithmica, 3:487--510, 1988.
• 5: Josep Díaz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002 [doi>10.1145/568522.568523]
• 6: Yefim Dinitz , Shimon Even , Roni Kupershtok , Maria Zapolotsky, Some compact layouts of the butterfly, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305626]
• 7: D. Dolev, T. Leighton, and H. Trickey. Planar embedding of planar graphs. In F. P. Preparata, editor, Advances in Computing Research, volume 2, pages 147--161. JAI Press, 1984.
• 8: Guy Even , Sudipto Guha , Baruch Schieber, Improved approximations of crossings in graph drawings, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.296-305, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335340]
• 9: Michael R. Fellows , Michael A. Langston, On well-partial-order theory and its application to combinatorial problems of VLSI design, SIAM Journal on Discrete Mathematics, v.5 n.1, p.117-126, Feb. 1992 [doi>10.1137/0405010]
• 10: Michael Formann , Frank Wagner, The VLSI layout problem in various embedding models, Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, p.130-139, May 1991, Berlin, Germany
• 11: Ashim Garg , Michael T. Goodrich , Roberto Tamassia, Area-efficient upward tree drawings, Proceedings of the ninth annual symposium on Computational geometry, p.359-368, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161165]
• 12: A. Garg, M. T. Goodrich, and R. Tamassia. Planar upward tree drawings with optimal area. International Journal of Computational Geometry and Applications, 6(3):333--356, 1996.
• 13: D. Gordon, Efficient embeddings of binary trees in VLSI arrays, IEEE Transactions on Computers, v.36 n.9, p.1009-1018, Sept. 1987 [doi>10.1109/TC.1987.5009532]
• 14: A. Gregori, Unit-length embedding of binary trees on a square grid, Information Processing Letters, v.31 n.4, p.167-173, May 22, 1989 [doi>10.1016/0020-0190(89)90118-X]
• 15: Haim Kaplan , Ron Shamir, Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques, SIAM Journal on Computing, v.25 n.3, p.540-561, June 1996 [doi>10.1137/S0097539793258143]
• 16: F. T. Leighton. New lower bound techniques for VLSI. In Proceedings of the Twelfth-Second Annual IEEE Symposium on Foundations of Computer Science, pages 1--12, 1981.
• 17: Charles Eric Leiserson, Area-Efficient VLSI Computation, MIT Press, Cambridge, MA, 1997
• 18: F. S. Makedon, C. H. Papadimitriou, and I. H. Sudborough. Topological bandwidth. SIAM J. Alg. Disc. Meth., 6(3):418--444, July 1985.
• 19: Graph separators, with applications, Kluwer Academic Publishers, Norwell, MA, 2001
• 20: J. A. Storer. On minimal-node-cost planar embeddings. Networks, 14:181--212, 1984.
• 21: Atsushi Takahashi , Shuichi Ueno , Yoji Kajitani, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete Mathematics, v.127 n.1-3, p.293-304, March 15, 1994 [doi>10.1016/0012-365X(94)90092-2]
• 22: Atsushi Takahashi , Shuichi Ueno , Yoji Kajitani, Mixed searching and proper-path-width, Theoretical Computer Science, v.137 n.2, p.253-268, Jan. 23, 1995 [doi>10.1016/0304-3975(94)00160-K]
• 23: S. Tayu and S. Ueno. Efficient embeddings of binary trees with bounded proper pathwidth into paths and grids. IEICE Trans. Fundamentals, E80-A(1):183--192, January 1997.
• 24: L. G. Valiant. Universality considerations in VLSI circuits. IEEE Trans. Computers, C-30(2):135--140, 1981.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
VLSI layout, aspect ratio, cutwidth, graph embedding, graph layout, grid, tree