A condition for a maximal planar graph to have a unique rectangular dual and its application to VLSI floor-plan

The concept of a rectangular dual of maximal planar graph G provides an interesting approach to VLSI floor plans in hierarchical design strategies. In the approach, a rectangular dual yielding the most area-efficient floor plan has to be selected from among all rectangular duals of G. A systematic algorithm is described for enumerating all rectangular duals of G in O(|V|R|) time, where V and R are the sets of vertices and rectangular duals of G, respectively. This time complexity is achieved by using a condition for a maximal planar graph to have a unique rectangular dual, and it is asymptotically optimal in the sense that at least O(|V|R|) time is necessary to output all the rectangular duals