10/01/1995 09:00 AM
Computer Engineering
Many practical routing problems such as BGA, PGA and test fixture routing involve routing two-terminal nets on a plane with exchangeable pins. In this paper, we unify these different problems as instances of the Planar Interchangeable 2-Terminal Routing (PI2TR) problem. We formulate the problem as flows in a routing network. Secondly, we show that PI2TR is NP-complete by reduction from satisfiability. Finally, we show experimental evidence that a simple min-cost flow heuristic considering only the most important cuts in the design can quickly produce routable results in most practical cases. The flow formulation can be generalized to multiple layers with no additional vias.
