An efficient two-dimensional compaction algorithm for VLSI symbolic layout

The 2-dimensional compaction problem for VLSI symbolic layout is considered. Through carefully arranging the constraints among the elements which are represented as rectangles and the compaction strategies including the basic 2-dimensional compaction and the jog, the goal to compact the layout so that its bounding rectangle has a minimum or an approximately minimum area, is achieved. A systematical search method is recommended to find the proper jog points on the wires. A reversed compaction is used to optimize the compacted result. The procedure of designers´ work is fully considered in order to accelerate the compacting process