Via Minimization for Gridless Layouts

This paper describes a graph theoretic algorithm which, given a particular layout, finds a layer assignment that requires the minimum number of vias. The time complexity of the algorithm is O(n ³) where n is the number of routing segments in the given layout. Unlike previous algorithms, this algorithm does not require the layout to be grid based and places no constraints on the location of vias or the number of wires that may be joined at a single junction. The algorithm yields globally optimum results when the maximum junction degree is limited to three and has been fully implemented.