A generic algorithm for one-dimensional homotopic compaction

One-dimensional homotopic compaction problems model the task of VLSI layout compaction with automatic jog insertion. They have the following form: given a routable layout, find a layout of minimum width reachable by a continuous motion of layout components that displaces each rigid component horizontally and preserves routability. We define a configuration space for this problem, and prove that if routability is characterized bycut conditions, then the set of reachable configurations is a closed, convex polyhedron. We also present a polynomial-time algorithm that finds the constraints defining this polyhedron and solves them to produce an optimal configuration. A homotopic router can recover the compacted layout from this configuration. We illustrate our strategy in thesketch model of VLSI layout, where it yields a compaction algorithm with worst-case running timeO(N ⁴) on input of sizeN.