Title:
A Faster One-Dimensional Topological Compaction Algorithm
with Jog Insertion
Hsiao-Feng Steven Chen
Avant! Corporation
46871 Bayside Parkway
Fremont, CA 94538
schen@avanticorp.com
D. T. Lee*
Department of Electrical and Computer Engineering
Northwestern University
Evanston, IL 60208 USA
dtlee@ece.nwu.edu
* Supported in part by the National Science Foundation under the
Grants CDA-9703228 and CCR-9731638, and by the Office of Naval
Research under the Grants No. N00014-95-1-1007 and No. N00014-97-1-0514.
Abstract:
We consider the problem of one-dimensional topological compaction with jog
insertions. By combining both geometric and graph theoretic approaches
we present a faster and simpler algorithm to improve over previous results.
The compaction algorithm takes as input a sketch consisting of a set $F$
of features and a set $W$ of wires, and minimizes the horizontal width of
the sketch while maintaining its routability.
The algorithm consists of the following steps: constructing a horizontal
constraint graph, computing all possible jog positions, computing the
critical path, relocating the features and reconstructing a new sketch
homotopic to the input sketch, which is suitable for detailed routing.
The algorithm runs in $O(|F|\cdot |W|)$ worst-case time and space,
which is asymptotically optimal in the worst case. Experimental results
are also presented.
Algorithmica, (28,4) Dec. 2000, pp. 390-421.