Rectangular Dualization
The idea
Most methods optimize wirelength and let adjacency fall where it may. Rectangular dualization inverts the question. Suppose you already know which blocks must be adjacent: heavy buses between them, shared power domains, abutted datapaths. Represent that as a graph: one vertex per block, one edge per required adjacency.
A rectangular dual of that graph is a dissection of the die into one rectangle per block whose shared walls are exactly the graph's edges. Two rectangles share a wall when, and only when, their blocks are joined by an edge; no two rectangles touch otherwise.
Graph theory gives an exact test for when such a floorplan exists. Treat the adjacency graph as a planar triangulated graph: planar, with every internal face a triangle. It has a rectangular dual if and only if it contains no separating triangle, a three-cycle with graph vertices both inside and outside it. A separating triangle makes a dual impossible, and its absence guarantees one can be built.
Kozminski and Kinnen gave the construction algorithm in 1984. Later work added sizing: once the topology is fixed, choosing wall positions so each block reaches its required area is a linear program.
The recipe
Step 1 (extract adjacency). From the netlist and constraints, build the adjacency graph: one node per block, one edge per required adjacency.
Step 2 (planarize and triangulate). Reduce the graph to a planar triangulated graph, the form the existence theorem applies to.
Step 3 (check). Test for a separating triangle. If one exists, no rectangular dual exists and the adjacency requirement must be relaxed.
Step 4 (construct). Build the rectangular dual, one rectangle per node, with a shared wall for every edge.
Step 5 (size). Solve a linear program for the wall positions so every block reaches its target area, keeping all adjacencies fixed.
Watch it work: graph to floorplan and back
A four-block adjacency graph, its rectangular dual, the check that every edge is a shared wall, the separating-triangle case that has no dual, and the area-sizing step.
Pros, cons, and the trade-off
Strengths
- Adjacency is exact: when the specification is which blocks must touch, the dual realizes it precisely, which no wirelength method guarantees.
- A decidable condition: the separating-triangle test says exactly whether a valid floorplan exists.
- Sizing is tractable: with the topology fixed, meeting target areas is a linear program.
Weaknesses
- Needs a planar adjacency requirement: real netlists are neither planar nor triangulated, so a preprocessing step must extract one, and quality depends on that extraction.
- Adjacency, not wirelength: the method optimizes literal adjacency, while most designs care about total wirelength.
- Can be infeasible: a separating triangle means the requested adjacencies simply cannot all be met.
The trade-off
Rectangular dualization models adjacency exactly and models nothing else. When adjacency is the specification, it is the method that fits: it provides a clear feasibility test and tractable area sizing. When the specification is wirelength, the adjacency graph must first be derived from the netlist, and the quality of the result is bounded by the quality of that derivation.
Is it actually used today?
The evidence for rectangular dualization is in adjacency-driven domains and in floorplan theory, not in mainstream wirelength-driven flows.
- Analog and constraint-driven layout: floorplans with matching, symmetry, and abutment requirements, where adjacency is part of the specification.
- Related domains: some 3D-integration partitioning work and architectural floorplanning use rectangular duals.
- Floorplan theory: the duals reappear in mosaic floorplan enumeration, where counting floorplans is counting certain duals.