A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called rectangular drawings or floorplans. It is known that the number of rectangular drawings R(n) is asymptotically approximated by a geometric progression, where n is the number of inner rectangles. More precisely, there exists a constant c = limn→∞R(n)1/n. The best upper and lower bounds of c ever known are 25 and 11.56, respectively. In this report, R(n) ≤ 13.5n−1is shown, which implies c ≤ 13.5.

We present an ordered tree (O tree) structure to represent nonslicing floorplans. The O tree uses only n(2+[lg n]) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both x and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n!2/sup 2n-2//n/sup l.5/). This is very concise compared to a sequence pair representation that has O((n!)/sup 2/) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n/sup 2/(n/4e)/sup n/). The complexity of O tree is even smaller than a binary tree structure for slicing floorplan that has O(n!2/sup 5n-3//n/sup 1.5/) combinations. Given an O tree, it takes only linear time to construct the placement and its constraint graph. We have developed a deterministic floorplanning algorithm utilizing the structure of O tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over previous central processing unit (CPU) intensive cluster refinement method.

Abstract|In the rectangle packing problem, encoding schemes to represent the placements of rectangles are the key factors of ecient algorithms.In 1995, an epoch-making encoding scheme, known as SEQ-PAIR, was developed[2].The solution space of SEQ-PAIR has been considered suciently small.In this paper, however, we present a simple and natural encoding scheme of rectangle packings whose solution space is smaller than that of SEQ-PAIR.

In the rectangle packing problem, encoding schemes to represent the placements of rectangles are the key factors determining the efficiency of algorithms. SEQ-PAIR is one of the most sophisticated encoding scheme, which has been considered to have a small solution space. In this paper, we begin with a packing procedure that does not look so smart. This procedure, however, leads us to another encoding scheme DS (the abbreviation for Dropping Schedule) whose solution space has the same size as that of SEQ-PAIR. Moreover, we introduce encoding scheme LOT as an advanced version of DS, which has a smaller solution space.