A graph-theoretic via minimization algorithm for two-layer printed circuit boards

Based on graph theory, an efficient via minimization algorithm for certain types of two-layer printed circuit boards is developed which can be executed in polynomial time. The algorithm yields solutions for routings with junctions of degrees varying from 2 to 8 and guarantees the minimum number of vias for routings with three or fewer line segments connected to each junction. Examples are given to illustrate various aspects of the algorithm. In addition, preassignment of line segments on a particular layer of the board due to certain prescribed board (or component) constraints is discussed.