This well-written paper considers the problem of wiring together, in one layer, :In corresponding pairs of terminals that are located in two parallel rows on opposite sides of a channel. The channel width may either be fixed or variable. The variable width case is solved by finding the fixed width case for each possible width. The wiring models used are the river routing model and its generalizations. The :Iinternal wiring model is one in which each wire is completely inside the channel. This is identical to the river routing model, which is studied independently by a number of researchers see [1]. The :Iinternal-external wiring model is one in which each wire is either completely inside or completely outside the channel area. The main objective is to minimize the wiring area and the number of tracks used. The paper gives polynomial time algorithms for each of these problems. Furthermore, it shows that more compact wiring (i.e., less area) may be obtained by using the internal-external model instead of the internal model. More specifically, a savings factor of 0(n:S1/2) in area is achievable. Finally, it is shown how the solution to the one layer internal-external problem can be used to obtain a wiring according to the two layer internal model.

References

[1] Dolev, D.; Karplus, K.; Siegel, A; Strong, A.; and Ullman, J.D. Optimal wiring between rectangles, Proc. 13th annual ACM symposium on theory of computing (Milwaukee, WI, May 11-13, 1981), ACM, New York, 1981, 312-317.