One-layer routing without component constraints

摘要

We consider the problem of wiring together, in one layer, corresponding pairs of terminals located on either a printed circuit board (PCB) or on a VLSI chip. We assume that the terminals are located in two parallel rows on opposite sides of a channel. The channel width may either be fixed or variable. We further assume that the components (on which the terminals lie) do not restrict the routing. Corresponding to various natural restrictions that may be placed on the wiring, we define two classes of layouts and give polynomial-time algorithms which produce optimal layouts within the respective classes. In addition, we derive bounds which show that the layouts in one class may be significantly more compact than those in the other. The results which we present are applicable to PCB technology without qualification. With respect to VLSI technology, the results are applicable provided that a separate layer is available for routing. That is, a layer which is effectively insulated from the active circuits of the components. In addition, we show how one-layer routings obtained under the no component constraint assumption can be utilized for two-layer routing under a conventional VLSI model (i.e., one with component constraints).