Floorplan representations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Floorplan representations: Complexity and connections

Full text

Pdf (576 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 8 , Issue 1 (January 2003) table of contents

Pages: 55 - 80

Year of Publication: 2003

ISSN:1084-4309

Authors

Bo Yao	University of California, San Diego, La Jolla, CA
Hongyu Chen	University of California, San Diego, La Jolla, CA
Chung-Kuan Cheng	University of California, San Diego, La Jolla, CA
Ronald Graham	University of California, San Diego, La Jolla, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 44, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/606603.606607 What is a DOI?

ABSTRACT

Floorplan representation is a fundamental issue in designing a floorplanning algorithm. In this paper, we first present a twin binary trees structure for mosaic floorplans. It is a nonredundant representation. We then derive the exact number of configurations for mosaic floorplans and slicing floorplans. Finally, the relationships between various state-of-the-art floorplan representations are discussed and explored.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Baxter, G. 1964. On fixed points of the composite of commuting functions. Proc. Amer. Math. Soc. 15, 6, 851--855.
	2	Yun-Chih Chang , Yao-Wen Chang , Guang-Ming Wu , Shu-Wei Wu, B*-Trees: a new representation for non-slicing floorplans, Proceedings of the 37th conference on Design automation, p.458-463, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337541]
	3	Chung, F. R. K., Graham, R. L., Hoggatt, Jr., V. E., and Kleiman, M. 1978. The number of Baxter permutations. J. Combin. Theor., Series A, 24, 3 (May), 382--394.
	4	S. Dulucq , O. Guibert, Baxter permutations, Discrete Mathematics, v.180 n.1-3, p.143-156, Feb. 1, 1998
	5	Etherington, I. M. H. 1940. Some problems of non-associative combinations. Edinburgh Math. Notes 32, pp. i--vi.
	6	Grason, J. 1970. A Dual Linear Graph Representation for Space-filling Location Problems of the Floor-Planning Type. MIT Press, Cambridge, MA.
	7	Pei-Ning Guo , Chung-Kuan Cheng , Takeshi Yoshimura, An O-tree representation of non-slicing floorplan and its applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.268-273, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309928]
	8	Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	9	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	10	Kozminsky, K. and Kinnen, E. 1985. Rectangular duals of planar graph. Networks, 15, 2, 145--157.
	11	Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
	12	Nakatake, S., Fujiyoshi, K., Murata, H., and Kajitani, Y. 1998. Module packing based on the BSG-structure and IC layout applications. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 17, 6 (June). 519--530.
	13	Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
	14	Ralph H. J. M. Otten, What is a floorplan?, Proceedings of the 2000 international symposium on Physical design, p.201-206, May 2000, San Diego, California, United States [doi>10.1145/332357.332400]
	15	Sakanushi, K. and Kajitani, Y. 2000. The quarter-state sequence (Q-sequence) to represent the floorplan and applications to layout optimization. In Proceedings of the IEEE Asia Pacific Conference on Circuits and Systems. 829--832.
	16	Antoni A. Szepieniec , Ralph H.J.M. Otten, The genealogical approach to the layout problem, Proceedings of the 17th conference on Design automation, p.535-542, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804582]
	17	Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan [doi>10.1145/370155.370523]

CITED BY 8

	Eyal Ackerman , Gill Barequet , Ron Y. Pinter, On the number of rectangular partitions, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Hayward H. Chan , Saurabh N. Adya , Igor L. Markov, Are floorplan representations important in digital design?, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Hayward H. Chan , Igor L. Markov, Practical slicing and non-slicing block-packing without simulated annealing, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Eyal Ackerman , Gill Barequet , Ron Y. Pinter , Dan Romik, The number of guillotine partitions in d dimensions, Information Processing Letters, v.98 n.4, p.162-167, 31 May 2006
	Eyal Ackerman , Gill Barequet , Ron Y. Pinter, A bijection between permutations and floorplans, and its applications, Discrete Applied Mathematics, v.154 n.12, p.1674-1684, 15 July 2006
	Eyal Ackerman , Gill Barequet , Ron Y. Pinter, On the number of rectangulations of a planar point set, Journal of Combinatorial Theory Series A, v.113 n.6, p.1072-1091, August 2006
	Renshen Wang , Evangeline F. Y. Young , Yi Zhu , Fan Chung Graham , Ronald Graham , Chung-Kuan Cheng, 3-D floorplanning using labeled tree and dual sequences, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Michael D. Moffitt , Jarrod A. Roy , Igor L. Markov , Martha E. Pollack, Constraint-driven floorplan repair, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-13, September 2008