A unified approach to the via minimization problem

A unified via minimization approach for two-layer routing of printed circuit boards and VLSI chips is presented. A topological routing strategy for the unconstrained via minimization (UVM) problem is proposed. Both the constrained via minimization (CVM) and the UVM problems are treated under a unified {0,1} linear programming formulation. The proposed practical algorithm can handle both grid-based and grid-less routing. Also, an arbitrary number of wires is allowed to intersect at a via and both Manhattan and knock-knee routings are included in the treatment. Compared with existing algorithms, the proposed algorithm is a unified one and computationally efficient. The time and space complexities of the algorithm are O(nlog n+k) and O(n+k), respectively, where n is the number of layout objects and k is the total number of cross points, knock-knee points and via candidates