Area minimization for hierarchical floorplans

In this paper we study the area-minimization problem for hierarchical floorplans. We settle an open problem on the complexity of the area-minimization problem for hierarchical floorplans by showing it to be NP-complete (even for balanced hierarchical floorplans). We then present a new algorithm for determining the nonredundant realizations of a wheel. The algorithm has time costO(k2 logk) and space cost0(k2) if each block in a wheel has at mostk realizations. Based on the new algorithm for a wheel, we design a new pseudopolynomial area-minimization algorithm for hierarchical floorplans of order-5. The time and space costs of the algorithm are0((nM)2log(nM) and0(n2M), respectively, wheren is the number of basic blocks andM is an upper bound on the dimensions of the realizations of the basic blocks. The area-minimization algorithm was implemented. Experimental results show that it is very fast.