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.