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.