IEEE Transactions on Computers · 1984 · 51 citations · 3 references
ComputingComputer EngineeringComputer ScienceAlgorithmsInterconnection NetworksTheory Of ComputationCombinatorial OptimizationComputational ComplexityGraph AlgorithmsGraph TheoryRoutingRouting AlgorithmsComputational Complexity Of Graph AlgorithmsPlanar Graph AlgorithmsRouting ComplexityRouting Problems
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.
3
Planar Formulae and Their Uses
David Lichtenstein · SIAM Journal on Computing · 1982 · 754 citations
The equivalence of theorem proving and the interconnection problem
James F. Lynch · ACM SIGDA Newsletter · 1975 · 152 citations