Complexity of Single-Layer Routing
Richards · IEEE Transactions on Computers · 1984
The problem of routing wires between pairs of terminals over a two-dimensional grid is shown to be NP-complete. Actually, the stronger result of routing over any planar graph with no vertex having degree greater than 3 is shown to be NP-complete.