PLANAR CONSTRAINED TERMINALS OVER-THE-CELL ROUTER

The authors present a new routing model for over-the-cell channel rout ing. A graph theoretical algorithm is then proposed to solve the new p roblem, The algorithm has a complexity of O(nk(2)), where n is the num ber of nets and k is the number of columns in the channel. It achieved a routing area reduction of 71.5% for the PRIMARY 1 benchmark example from MCNC, using three-layer over-the-cell routing. To resolve a sub- problem, the authors also present an O(m nu) algorithm to find the max imum weight independent chord set in a circle graph with m chords inci dent to nu vertices, where two chords may share a common vertex.