Polynomial time Manhattan routing without doglegs - A generalization of Gallai's algorithm

Gallai's classical result on interval packing can be applied in VLSI routin g to find, in linear time, a:minimum-width dogleg-free routing in the Manha ttan model, provided that all the terminals are on one side of a rectangula r [1]. Should the terminals appear on two opposite sides of the rectangular , the corresponding "channel routing problem" is NP-complete [2, 3]. We generalize Gallai's result for the case if the terminals appear on two a djacent sides of the rectangular.