Abstract
We propose a novel technique for constructing a floorplan from an adjacency requirement — represented by a graphG. The algorithm finds a geometric dual ofG involving both rectangular and L-shaped modules. This is the first dualization technique which permits L-shaped modules. We can test inO(n 3/2) time ifG admits an L-shaped dual and construct one, if it exists, inO(n 2) time, wheren is the number of modules.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bhasker, J., and Sahni, S., A Linear Time Algorithm To Check for the Existence of a Rectangular Dual of a Planar Triangulated Graph,Networks, Vol. 17, pp. 307–317, 1987.
Bhasker, J., and Sahni, S., A Linear Algorithm To Find a Rectangular Dual of a Planar Triangulated Graph,Algorithmica, Vol. 3, pp. 247–278, 1988.
Hakimi, S. L., and Schmeichel, E. F., On the Number of Cycles of LengthK in a Maximal Planar Graph,Journal of Graph Theory, Vol. 3, No. 1, pp. 69–86, 1979.
Harary, F.,Graph Theory, Addison-Wesley, Reading, MA, 1969.
Itai, A., and Rodeh, M., Finding a Minimum Circuit in a Graph,SIAM Journal of Computing, Vol. 7, No. 4, pp. 413–423, 1978.
Kozminiski, K., and Kinnen, E., Rectangular Dual of Planar Graphs,Networks, Vol. 15, pp. 145–157, January 1985.
Kozminski, K., and Kinnen, E., Rectangular Dualization and Rectangular Dissections,IEEE Transactions on Circuits and Systems, Vol. 35, No. 11, pp. 1401–1416, November 1988.
Lai, Y. T., and Leinwand, S. M., Algorithms for Floorplan Design via Rectangular Dualization,IEEE Transactions on Computer-Aided Design, Vol. 7, No. 12, pp. 1278–1289, December 1988.
Lee, C. Y., An Algorithm for Path Connections and Its Applications,IRE Transactions on Electronic Computers, Vol. 10, pp. 346–365, September 1961.
Otten, R. H. J. M., Graphs in Floor-Plan Design,International Journal of Circuit Theory and Applications, Vol. 16, pp. 391–410, 1988.
Preas, B. T., and Karger, P. G., Placement, Assignment and Floorplanning,Physical Design Automation of VLSI Systems, ed. by Preas, B. T., and Lorenzetti, M. J., Benjamin/Cummings, Menlo Park, CA, pp. 87–155, 1988.
Tsukiyama, S., Koike, K., and Shirakawa, I., An Algorithm To Eliminate All Complex Triangles in a Maximal Planar Graph for Use in VLSI Floor-Plan,Proceedings of the International Symposium on Circuits and Systems, Philadelphia, PA, pp. 321–324, 1986.
Wong, D. F., and Liu, C. L., Floorplan Design of VLSI Circuits,Algorithmica, Vol. 4, No. 2, pp. 263–291, 1989.
Yeap, K. H., and Sarrafzadeh, M., Rectangular Dualization: 2-Bend Shapes Suffice,Proceedings of the 29th Allerton Conference, Montincello, IL, pp. 79–85, October 1991.
Yeap, K. H., and Sarrafzadeh, M., Sliceable Floorplans by Dualization,Second Great Lakes Computer Science Symposium, Kalamazoo, MI, pp. 41–47, November 1991.
Author information
Authors and Affiliations
Additional information
Communicated by F. Thomson Leighton.
This work was supported in part by the National Science Foundation under Grants MIP-8709074 and MIP-8921540. The research by Yachyang Sun was done while he was with Northwestern University.
Rights and permissions
About this article
Cite this article
Sun, Y., Sarrafzadeh, M. Floorplanning by graph dualization: L-shaped modules. Algorithmica 10, 429–456 (1993). https://doi.org/10.1007/BF01891831
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01891831