ABSTRACT
During the physical design of integrated circuits, multi-chip module substrates, and printed circuit and wiring boards, interconnections are generally formed by patterning conductive paths on two or more layers. Because the layers are usually separated by a thin insulator, holes or vias are formed to connect the conductive paths on different layers. Most existing routing algorithms produce a large number of vias because they solve the layer assignment problem by placing all horizontal line segments on one layer and all vertical line segments on the other. However, the number of vias should be kept small. This chapter discusses the via minimization problem and presents algorithms to reduce vias. A via is a particular junction where two or more layers are electrically interconnected. A valid layer assignment is a set of wire segments and vias inside the routing region that implements the definitions of the set of signal nets without violating the design rules.
