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.