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.