Abstract
We generalize earlier results in VLSI layout theory by considering variable aspect ratio embeddings for VLSI graphs. By aspect ratio we mean the ratio of the length of the longer side to the length of the shorter side of the bounding rectangle of the embedding. Our results are based on separators and bifurcators. We obtain embeddings with existentially optimal area and any desired aspect ratio. Additionally, we can obtain either bounded capacitive delay or existentially optimal minimax edge length in the embeddings; both of these features reduce delays in the circuit.
A special feature of our results on minimax edge length is that they unify earlier separator- and bifurcator-based results for square embeddings, and also provide a simplified lower bound proof.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. N. Bhatt and F. T. Leighton, A framework for solving VLSI graph layout problems,J. Comput. System Sci.,28(2) (1984), 300–343.
G. Bilardi, M. Pracchi, and F. Preparata, A critique and appraisal of VLSI models of computation,Proceedings of the CMU Conference on VLSI Systems and Computation (1981), pp. 81–88.
R. P. Brent and H. T. Kung, On the area of binary tree layouts,Inform. Process. Lett. (1980), 46–48.
P. Czerwinski, Optimal VLSI Graph Embeddings in Variable Aspect Ratio Rectangles, Master's thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana (1985).
F. T. Leighton, New lower bound techniques for VLSI,Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (1981), pp. 1–12.
C. E. Leiserson, Area-efficient graph layouts (for VLSI),Proceedings of the 21st Annual Symposium on Foundations of Computer Science (1980), pp. 270–281.
C. A. Mead and L. Conway,Introduction to VLSI Systems, Addison-Wesley, Reading, MA, 1980.
M. S. Paterson, W. L. Ruzzo, and L. Snyder, Bounds on minimax edge length for complete binary trees,Proceedings of the 13th Annual ACM Symposium on Theory of Computing (1981), pp. 293–299.
M. S. Pinsker, On the complexity of a concentrator,Proceedings of the 7th International Teletraffic Congress, 1973, pp. 318/1–318/4.
V. Ramachandran, Area-optimal graph embeddings for VLSI in rectangles of varying aspect ratio, Technical Report #301, EECS Department, Princeton University (1982).
V. Ramachandran, On driving many long wires in a VLSI layout,Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (1982), pp. 369–378; alsoJ. Assoc. Comput. Mach.,33(4) (1986), 687–701.
C. D. Thompson, A Complexity Theory for VLSI, Ph.D. thesis, Carnegie-Mellon University (1980).
L. G. Valiant, Universality considerations in VLSI circuits,IEEE Trans. Comput.,30(2) (1981), 135–140.
Author information
Authors and Affiliations
Additional information
Communicated by F. Thomson Leighton.
This research was supported in part by the Semiconductor Research Corporation under contract SRC RSCH 84-06-049 and by an IBM Faculty Development Award to Vijaya Ramachandran. Preliminary versions of portions of this work were presented at the Sixteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, February 1985, and at the 1985 Conference on Information Sciences and Systems, Baltimore, MD, March 1985.
Rights and permissions
About this article
Cite this article
Czerwinski, P., Ramachandran, V. Optimal VLSI graph embeddings in variable aspect ratio rectangles. Algorithmica 3, 487–510 (1988). https://doi.org/10.1007/BF01762128
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01762128