Polynomial time manhattan routing without doglegs : A generalization of Gallai's algorithm
Endre Boros, András Recski, Tibor Szkaliczki, Ferenc Wettl · SZTAKI Publication Repository (Hungarian Academy of Sciences) · 1999
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 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 adjacent sides of the rectangular.