An efficient layer assignment algorithm for gridless switchbox routing

A graph-theoretic algorithm is presented for the layer assignment and via minimization of a gridless switchbox routing. A concept called via propagation is used to facilitate the minimization of vias. The time complexity of the proposed algorithm is O(nlog n+K ), where n is the number of routing wire segments in the layout and K is the maximum number of vias that can occur. The approach achieves the minimum number of vias for several difficult switchbox problems