Title:
A Faster One-Dimensional Topological Compaction Algorithm
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
Grant CCR-9309743, and by the Office of Naval Research under the
Grant No. N00014-97-1-0514, and No. N00014-95-1-1007
Abstract:
We consider the problem of one-dimensional topological compaction with jog insertions.
Combining both geometric and graph theoretic approaches we present a faster and simpler
algorithm, improving 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 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.
Proc. Int'l Symposium on Algorithms and Computation, (ISAAC'97)
Singapore, Dec. 1997, pp. 303-313.