The partitioning of floorplans is an important topic in the field of very large-scale integration (VLSI) physical design automation. Proper partitioning of floorplans can lead to not only efficient insertion of repeaters, but also efficient global and channel routing. As a result, the quality of physical layouts can be improved and the design time can be reduced.

In this paper, a floorplan is defined to contain a number of rectangular blocks, and each of those blocks may have associated nets. An ms-cut is a monotone staircase that partitions rectangular blocks of a floorplan into two groups, and the monotone staircase cuts those blocks from the floorplan’s bottom-left corner to the floorplan’s top-right corner; the staircase does not go down or go left when it cuts the floorplan. Since a floorplan can have many different ms-cuts, there are a variety of problems with regard to the partitioning of a floorplan with ms-cuts.

A number of floorplan partitioning problems are discussed in the paper. The min-cut problem P_c is to find an ms-cut that minimizes the number of nets crossing the two partitions. The number-balance problem P_n is to find an ms-cut that balances the numbers of rectangular blocks for the two partitions, whereas the area-balance problem P_A is to find an ms-cut that balances the areas of the two partitions. Furthermore, there is the number-balanced min-cut problem P_nc and the area-balanced min-cut problem P_Ac; the two problems consider the number of crossing nets as well as one of the balancing factors.

Before this paper was published, it had already been proven that problems P_c and P_n are polynomial time solvable. The paper goes one step further and attacks other floorplan partitioning problems: it proves that P_A and P_Ac are nondeterministic polynomial time (NP) hard, and conjectures that P_nc is also NP hard. Furthermore, the paper proposes a heuristic for solving these difficult problems. The heuristic is based on a max-flow min-cut method, and is capable of partitioning (or bi-partitioning) a floorplan hierarchically.

The paper discusses a number of floorplan partitioning problems. These problems are clearly presented and are interesting. The heuristic proposed for solving some of these problems is flexible and efficient. Moreover, partitioning a floorplan using monotone staircase cuts can be beneficial to other VLSI physical design processes.