A PROVABLY GOOD MULTILAYER TOPOLOGICAL PLANAR ROUTING ALGORITHM IN IC LAYOUT DESIGNS

Given a number of routing layers, the multilayer topological planar routing problem is to choose a maximum (weighted) set of nets so that each net in the set can be topologically routed entirely in one of the given layers without crossing other nets. This problem has important applications in the layout design of multilayer IC technology which has become available recently. In this paper, we present a provably good approximation algorithm for the multilayer topological planar routing problem. Our algorithm, called the iterative-peeling algorithm, finds a solution whose weight is guaranteed to be at least 1 - (1/e) almost-equal-to 63.2% of the weight of an optimal solution. The algorithm works for multiterminal nets and arbitrary number of routing layers. For fixed number of routing layers, we have even tighter performance bounds. In particular, the performance ratio of the iterative-peeling algorithm is at least 75% for two-layer routing, and is at least 70.4% for three-layer routing. Experimental results confirm that our algorithm can always route a majority of the nets without using vias, even when the number of routing layers is fairly small.