Manhattan channel routing is attractive for practical applications in VLSI layout design. Because of its theoretical complexity no efficient algorithms that yield the optimum channel width can be expected to exist for the general case. Based on two lower bounds for channel width called density and flux Baker, Bhatt, and Leighton have designed an approximation algorithm that routes each two-terminal net problem with density d and flux f in a channel of width d+O(f) and each multiterminal net problem in a channel consisting of at most 2d+O(f) tracks. Several properties of that algorithm stand in the way of its immediate practical application. In contrast, good practical algorithms come additively within one or two of the density fairly often, but they have a terrible theoretical performance. The paper presents a new method for Manhattan routing, that approximates the optimum channel width to within a constant factor, but is superior to the method of Baker, Bhatt and Leighton with respect to the constant factor, the running-time, the number of generated jogs and the typical number of tracks used. Moreover, it can be adjusted to the practical structure of a channel. In this sense the present approximation algorithm is practical.
