Adjacent Constraint Graph

The idea

The Transitive Closure Graph carries every pairwise relation, up to n(n-1) edges of mostly redundant information. The Adjacent Constraint Graph asks: what is the least we can store and still be a constraint-graph representation? Its answer: keep only relations between blocks that are adjacent in the packing sense (no third block's projection separates them), subject to structural rules that ban redundant and crossing patterns. The result is a sparse pair of graphs that still determines the packing uniquely and decodes with the usual longest-path computation.

Sparsity buys three things: less memory, cheaper moves (fewer edges to fix up after a perturbation), and a cleaner geometric reading, since an edge now means "these two blocks actually see each other", which is the level at which physical constraints like abutment and channel insertion live.

Trade-offs

Maintaining the structural invariants under arbitrary moves is the delicate part; move design is more constrained than in the free-swapping sequence pair world. The representation sits deliberately between extremes: complete like the sequence pair and Transitive Closure Graph, sparse like the trees, at the cost of invariants more intricate than either.

Where you meet it today

In the later representation literature and in floorplanners for which adjacency is semantically load-bearing (channel planning, bus-driven floorplanning, some analog work). Historically it closes the 1995-2004 representation race: after the Adjacent Constraint Graph, the field's energy moved from inventing encodings to the fixed-outline and analytical problems of the modern era.