Title: A Faster Algorithm for Rubber-Band Equivalent Transformation for Planar VLSI Layouts 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-93-1-0272. Abstract: In this paper we consider the problem of transforming a single-layer topological routing of $n$ two-terminal nets into a rubber-band equivalent using rectilinear wires in the presence of rectilinear circuit modules. Given a topological planar VLSI layout sketch with |F| features and |W| non-crossing wire segments connecting n two-terminal nets, we present an O(|F|*|W|) time algorithm to do the vertex-disjoint rubber-band equivalent transformation of these n nets if it exists. The algorithm consists of two phases, computing a loose homotopy with four spokes matrices, and computing a vertex-disjoint rubber-band equivalent of the given homotopy, each phase taking O(|F|*|W|) time and space. Both complexities are asymptotically optimal in the worst case. From the vertex-disjoint rubber-band equivalent of the given homotopy, one can obtain the detailed routing within the same time complexity. Experimental results are also presented. Key Words: Planar VLSI Layouts, Rubber-Band Equivalent, Detailed Routing. IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, (15,2) Feb. 1996, pp. 217-227.