Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa -- Papers |
Fujimaki-Takahashi Squeeze: Linear Time Construction of Constraint Graphs of Floorplan for a Given Permutation*
1 The authors are with the Graduate School of Science and Technology, Niigata University, Niigata-shi, 950-2181 Japan. E-mail: takahasi{at}ie.niigata-u.ac.jp
A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.
Key Words: floorplan, representation, permutation, constraint graph
Manuscript received June 26, 2007. Manuscript revised October 5, 2007.
* The original paper was presented at the 20th Karuizawa Workshop (2007) and submitted to the 14th Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI 2007).
Reference
[1] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangle-packing-based module placement," Proc. ACM/IEEE ICCAD, pp.472–479, 1995. [2] H. Murata, K. Fujiyoshi, T. Watanabe, and Y. Kajitani, "A mapping from sequence-pair to rectangular dissection," Proc. IEEE ASP-DAC, pp.625–633, 1997. [3] T. Shimizu, The Rectangular Dissection (Kukei-Bunkatsu), Nippon Hyoronsha, 1999. [4] E. Ackerman, G. Barequet, and R.Y. Pinter, "On the number of rectangular partitions," Proc. SODA, pp.736–745, 2004. [5] K. Sakanushi, L. Jin, M. Tsuboi, and Y. Kajitani, "A new data structure of the room-room adjacency floorplan," Proc. 14th Workshop on Circuits and Systems in Karuizawa, pp.255–260, 2001. [6] X. Zhang and Y. Kajitani, "Space-planning: Placement of modules with controlled empty area by single-sequence," Proc. IEICE ASP-DAC, pp.25–30, 2004. [7] Y. Kajitani, "Theory of placement by numDAG related with single-sequence, SP, BSG, and O-tree," Proc. IEEE ISCAS, pp.4471–4474, 2006. [8] R. Fujimaki and T. Takahashi, "A surjective mapping from permutations to room-to-room floorplans," IEICE Trans. Fundamentals, vol.E90-A, no.4, pp.823–828, April 2007.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by TAKAHASHI, T.
Articles by FUJIMAKI, R.
Search for Related Content
Social Bookmarking
What's this?