The rectangular dual of a plane graph G has applications in the floor planning of VLSI circuits and in architectural design. Each vertex of the graph G represents a circuit module and the edges represent adjacencies between modules. A rectangular dual provides a placement of the circuit modules that preserves the required adjacencies. Recent works in VLSI circuit layout field have focused on the problem of finding a rectangular dual satisfying the given constraints with the area as small as possible.
A rectangular dual is said to be a slicing if it contains a single rectangle or if there exists a vertical or a horizontal cut that divides the slicing into two parts, each of which is also a slicing. Circuit layouts with slicing structures are always free of cyclical routing conflicts, thus a channel ordering for detailed routing can always be found. Moreover, the rectangular dualization with slicing structures is useful for top-down hierarchical layouts.
Previous works on the rectangular dualization have dealt only with rectangular duals that admit nonslicing structures which cannot represent hierarchical structures. In this thesis, we present an algorithm to find a rectangular dual with a slicing structure if it exists. Then we also give an algorithm to locate each vertex of rectangular dual at a grid point as compact as possible. Using these algorithms, the rectangular dual can be drawn with the slicing structure in a grid within the area of the optimal size in the worst case. In addition, we suggest several patterns that cannot be drawn with slicing structures.
