Transitive Closure Graph
The idea
Every representation on these pages eventually produces two constraint graphs: a horizontal one saying "block a is left of block b" and a vertical one saying "a is below b". The transitive closure graph skips the encoding and keeps the graphs themselves as the representation.
For every pair of blocks it stores exactly one relation, left-of or below, as a directed edge in one of two graphs:
| graph | edge i to j means |
|---|---|
| Ch (horizontal) | block i is left of block j |
| Cv (vertical) | block i is below block j |
Both graphs are kept transitively closed: if a is left of b and b is left of c, the edge a to c is materialized too. Because every pair sits in exactly one graph, the two graphs together fix the relative position of everything, with no coordinates stored.
Decoding is a longest-path pass. Weight each Ch node by its block width and the longest path to a node is its x-coordinate; do the same on Cv with heights for y. The longest path overall gives the chip width and height. It is the same packing step the sequence pair uses, run directly on the stored graphs.
The recipe
Step 1 (relations). For each pair of blocks, record one edge: left-of in Ch or below in Cv.
Step 2 (close). Add every edge implied by transitivity, so both graphs are transitively closed and acyclic.
Step 3 (pack x). Longest path on Ch weighted by widths gives every x-coordinate.
Step 4 (pack y). Longest path on Cv weighted by heights gives every y-coordinate.
Step 5 (perturb). For annealing, edit the graphs directly: reverse an edge (make b left of a), move a relation between the graphs (turn left-of into below), rotate a block, or swap two vertices. Restore the closure locally and the graphs stay acyclic, so the result is always feasible.
Watch it work: two graphs and a longest-path pack
Four blocks. The walkthrough reads the left-of and below relations off the placement, builds the horizontal graph Ch and the vertical graph Cv (marking the edge that transitive closure adds), then packs by longest path on each graph to recover the coordinates.
Pros, cons, and the trade-off
Strengths
- Relations are explicit: the geometry is readable straight off the graphs, no decoding from permutations.
- Constraints are just edges: abutment, alignment, and boundary requirements are added as required edges, which the sequence pair cannot do as directly.
- Always feasible: the closed graphs are acyclic by construction, so every move yields a legal placement.
- Fully general: it represents all packings including those with slack, and is provably interconvertible with the sequence pair.
Weaknesses
- Large state: the closure holds up to n(n-1)/2 edges per graph, more memory than the tree representations.
- Bookkeeping per move: each move must restore the transitive closure, which costs more than a tree surgery.
- Evaluation overhead: carrying the closure around motivated the TCG-S variant, which couples the graphs with a sequence for faster, incremental cost updates.
The trade-off
The transitive closure graph trades compactness for transparency and constraint power. Where the tree representations store a few pointers and derive relations on decode, this stores all the relations explicitly and keeps them closed. That makes placement constraints as simple as adding an edge and keeps every move feasible, at the cost of larger state and closure bookkeeping. It is the representation to reach for when constraints, not raw encoding size, dominate.
Is it actually used today?
The transitive closure graph is a general-purpose research representation and the sequence pair's main rival for non-slicing floorplans.
- Constraint-heavy floorplanning: it is a natural fit where abutment, alignment, boundary, and bus-planning constraints must be enforced, since each reads directly as a required edge.
- Sequence-pair alternative: it appears throughout the 2000s floorplanning literature as the graph-based counterpart to the sequence pair, with the TCG-S variant added for speed.
- Analog and constrained placement: the explicit relations make it a common base for symmetry- and constraint-aware placement research.
- Note on production tools: commercial floorplanners do not publish their internal representations, so any specific use there is not verifiable. The evidence above is the academic record.