A New Method for Floor Planning Using Topological Constraint Reduction

Abstract

We discuss a new approach to the constraint-based floor planning of flexible, fixed, and preplaced blocks based on the removal of redundant constraints and the reshaping of flexible blocks. A floor plan is said to respect a given constraint set if it satisfies either a vertical or a horizontal constraint in the set for each pair of blocks. Our approach is to construct a floor plan of optimal area that respects the input constraint set. The input constraint set is assumed to be derived from a relative placement of the blocks. We present motivations for considering this new approach and describe a heuristic floor-planning algorithm based on constraint reduction and block reshaping. We present a simple example to illustrate the algorithm. We also give several real floor-planning examples. © 1991 IEEE