Compaction

feature + mask

3 ways to reduce layout area:
- reduce spacing betw. features
- reduce feature size
- reshape feature

design rules:
- spacing constraint
- grouping constraint (e.g. via + wire==>sliding ports)
- compatibility (pi)
- diverse constraint (max distance btw features)


Variations:
- 1-D compaction and 2-D compaction
- Constraint-graph based compaction vs. virtual grid based compaction
- packing is a special case where M=1, dij=0, pi=id




constraint generation - why O(n^2)?
- scan-line
- shadow propagation

Constraint solving:
- union-find alg.
- how to deal with equality constraints?
- how to deal with cycles?

compression ridge method

- tile graph to encode empty space + max-flow alg.

-



Layout graph

- generate graph

-- plane-sweep (bottom-to-top scan)

--- include compatibility relation

-- branch-and-bound

- find longest path

-- Dijkstra vs. Bellman-Ford





Topological Compaction