ON CROSSING MINIMIZATION PROBLEM

In this paper, we consider a problem related to global routing postopt imization: the crossing minimization problem (CMP), Given a global rou ting representation, the CMP is to minimize redundant crossings betwee n every pair of nets. In particular, there are two kinds of CMP: const rained CMP (CCMP) and unconstrained CMP (UCMP). These problems have be en studied previously in [11] where an O(m(2)n)i algorithm was propose d for CCMP, and in [15] where an (mn(2) + xi(2)) algorithm was propose d 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 r outing topology, We present a simpler and faster O(mn) algorithm for C CMP and an O[n(m + xi)] time algorithm for UCMP, Both algorithms impro ve over the time bounds of the previously proposed algorithms. The nov el part of our algorithm is that it uses the plane embedding informati on of globally routed nets in the routing area to construct a graph-ba sed framework and obtain a good junction terminal assignment that mini mizes the number of crossings.