Title: On Crossing Minimization Problem 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 Avant! Corporation and by the Office of Naval Research under the Grant No. N00014-97-1-0514. Abstract: In this paper we consider a problem related to global routing post-optimization: the crossing minimization problem (CMP). Given a global routing representation, the CMP is to minimize redundant crossings between every pair of nets. In particular, there are two kinds of CMP: constrained CMP (CCMP) and unconstrained CMP (UCMP). These problems have been studied previously in [Groe-89], where an $O(m^2n)$ algorithm was proposed for CCMP, and in [MaSa-95], where an $(mn^2 + \xi^2)$ algorithm was proposed for UCMP, where $m$ is the total number of modules, $n$ is the number of nets, and $\xi$ is the number of crossings defined by an initial global routing topology. We present a simpler and faster $O(mn)$ algorithm for CCMP and an $O(n(m + \xi))$ time algorithm for UCMP. Both algorithms improve over the time bounds of the previously proposed algorithms. The novel part of our algorithm is that it uses the plane embedding information of globally routed nets in the routing area to construct a graph-based framework and obtain a good junction terminal assignment that minimizes the number of crossings. Key Words: Crossing Minimization, Global Routing, Homotopy, Topology, VLSI Layout. IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, 18(4):463-474, April 1999.