Three-layer bubble-sorting-based nonManhattan channel routing

It is well known that a nonManhattan channel router can use fewer routing t racks, and is never worse than a Manhattan router in a channel. To my knowl edge, a three-layer bubble-sorting-based nonManhattan channel routing probl em is always solved by the solution in a two-layer bubble-sorting-based non Manhattan channel routing problem. Recently, an O(kn(2)) heuristic algorith m [Chaudhary et al. 1991] and an O(k(2)n) optimal algorithm [Chen et al. 19 94] have been proposed, where k is the number of two-layer routing tracks a nd n is the number of terminals in a bubble-sorting-based nonManhattan chan nel. In this paper we propose an optimal three-layer bubble-sorting-based n onManhattan routing algorithm to minimize the number of three-layer routing tracks. Furthermore, the time complexity of this optimal algorithm is prov en to be in O(hn) time, where h is the number of three-layer routing tracks and n is the number of terminals in a bubble-sorting-based nonManhattan ch annel.