Algorithms for floorplan design via rectangular dualization

A rectangular floorplan construction problem is approached from a graph-theoretical view. The study is based on a reduction of the rectangular dualization problem to a matching problem on bipartite graphs. This opens the way to applying traditional graph-theoretic methods and algorithms to floorplanning. Another result is a method for generating alternative rectangular duals, such that a proposed floorplan can be optimized by a sequence of iterative transformations. This approach is made more practical than others, by assuming that the given structure graph can be modified to force it to admit a rectangular dual. Algorithms that introduce edges and vertices into the given graph until a rectangular dual can be constructed are also presented