Polynomial time manhattan routing without doglegs - a generalization of gallai's algorithm

Abstract

Gallai's classical result on interval packing can be applied in VLSI routing to find, in linear time, a minimum/width dogleg/free routing in the Manhattan model, provided that all the terminals are on one side of a rectangular [1]. Should the terminals appear on two opposite sides of a 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 adjacent sides of the rectangular.