Manhattan Channel Routing is NP-complete Under Truly Restricted Settings
Martin Middendorf · 1996
Settling an open problem that is over ten years old, we show that Manhattan channel routing - with doglegs allowed - is NP-complete when all nets have two terminals. This result fills the gap left by Szymanski [Szy85], who showed the NP-completeness for nets with four terminals. Answering a question posed by Schmalenbach [Sch90] and Greenberg, J#j#, and Krishnamurty [GJK92], we prove that the problem remains NP-complete if in addition the nets are single-sided and the density of the bottom nets is at most one. Moreover, we show that Manhattan channel routing is NP-complete if the bottom boundary is irregular and there are only 2-terminal top nets. All of our results also hold for the restricted Manhattan model where doglegs are not allowed.