"Manhattan Channel Routing is NP-complete Under Truly Restricted Settings."

Martin Middendorf (1996)
a service of Schloss Dagstuhl - Leibniz Center for Informatics