Optimal via minimisation by selection of layer assignment and routing ordering in a bubble-sorting-based non-Manhattan channel

It is well known that a non-Manhattan channel router never uses more tracks than a Manhattan router in a channel. For a bubble-sorting-based non-Manhattan channel, all the nets can be routed by k bubble-sorting swap passes in an optimal bubble-sorting solution, and these k swap passes can be further mapped onto k 1-track-routing processes in a two-layer routing model. However, these proposed bubble-sorting-based non-Manhattan routers do not consider an optimal routing ordering for physical mapping of the k swap passes, and redundant vias are yielded in a random routing ordering. Based on the result of k swap passes in an optimal bubble-sorting solution: (i) optimal via minimisation by the selection of layer assignment and routing ordering in a bubble-sorting-based non-Manhattan channel is proposed; and (ii) the time complexity of this proposed algorithm is proven to be in O(k²) time, where k is the number of swap passes in an optimal bubble-sorting solution.