Dogleg Channel Routing is NP-Complete

Abstract

Interconnecting two rows of points across an intervening channel is an important problem in the design of LSI circuits. The most common methodology for producing such interconnections uses two orthogonal layers of parallel conductors and allows wires to "dogleg" arbitrarily. Although effective heuristic procedures are available for routing channels with this methodology, no efficient optimal algorithm has yet been discovered for the general case problem. We show that such an algorithm is unlikely to exist by establishing that this problem is NP-complete.