On Routing Two-Point Nets Across a Channel

Many problems that arise in general channel routing manifest themselves in simpler situations. We consider connecting a set of n terminals on a line to another set on a parallel line across a rectangular channel. We show that in any solution to the problem that (almost) minimizes the width of the channel (i.e. the distance between the lines the terminals reside on), (i) a net may require as many as O(vn) jogs, (ii) no net routed from top to bottom need ever turn upward in the middle. We also present an efficient algorithm to obtain minimal jogging in river routing, and provide necessary and sufficient conditions for conflict cycle resolution. These and other results are presented in the context of a general survey on routing from a combinatorial complexity point of view.