Bounds on the number of slicing, mosaic, and general floorplans

A floorplan can be defined as a rectangular dissection of the floorplan region. Simple and tight asymptotic bounds on the number of floorplans for different dissection structures help us to evaluate the size of the solution space of different floorplan representation. They are also interesting theoretically. However, only loose bounds exist in the literature. In this paper, we derive tighter asymptotic bounds on the number of slicing, mosaic and general floorplans. Consider the floorplanning of n blocks. For slicing floorplan, we prove that the exact number is n!((-1)/sup n+1//2)~/sub k=0//sup n/(3+(radical)8)/sup n-2k/(/sub k//sup 1/2/)(/sub n - k//sup 1/2/) and the tight bound is (theta)(n!2/sup 2.543n//n/sup 1.5/) [9] . For mosaic floorplan, we prove that the tight bound is (thetal)(n!2/sup 3n//n/sup 4/). For general floorplan, we prove a tighter lower bound of (omega)(n!2/sup 3n//n/sup 4/) and a tighter upper bound of O(n!2/sup 5n//n/sup 4.5/).