Complexity of Single-Layer Routing

Richards

IEEE Transactions on Computers · 1984 · 51 citations · 3 references

Concepts

Abstract

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.

References

3