Floorplanning by graph dualization: L-shaped modules

A technique for constructing a floorplan from an adjacency requirement-represented by a graph G-is proposed. The algorithm finds a geometric dual of G involving both rectangular and L-shaped modules. The algorithm tests in O(n^3/2) time if G admits an L-shaped dual and can construct one, if it exists, in O(n²) time, where n is the number of modules. An example of how the algorithm constructs an L-shaped dual of a graph G with 14 nodes is shown