An Algorithm for Finding a Rectangular Dual of a Planar Graph for Use in Area Planning for VLSI Integrated Circuits
Krzysztof Koźmiński, E. Kinnen · Design Automation Conference · 1984
An O(n /sup 2/) algorithm for finding a rectangular dual of a planar triangulated graph is presented. In practice, almost linear running times have been observed. The algorithm is useful for solving area planning problems in VLSI IC design.