Width-reduction for a linear time channel routing algorithm

Abstract

This paper presents a new upper bound for channel routing of multiterminal nets on two layers. The result, which is essentially the improving of Recski and Strzyzewski's algorithm [2], works in linear time and uses width at most 4l/3, where l is the length of the channel. (The aforementioned algorithm used width at most 3l/2.)

In 1994, Gao and Kaufmann [1] presented a new algorithm for channel routing of multiterminal nets on two layers, which required 3d/2 + O (  ) tracks, where d was the density of the channel routing problem. The result of this paper is better than this, if d is very close to its upper bound, namely to l. In fact, this is rarely the case.