On Single Layer Routing with no Wires Passing between Adjacent Pins.

This paper examines whether a circuit is realizable on a single-layer printed wiring board. Linear time algorithms for this problem have been proposed under the constraint that no wiring is permitted below the mounted modules. However, this problem becomes NP-complete when wiring below the mounted modules is permitted and the number of wires available between adjacent pins of a module is given. This paper presents an algorithm for this problem under the constraint that wiring is permitted under modules but no wires are allowed to pass between adjacent pins. The time complexity of this algorithm is proportional to the total number of pins of the circuit. [ABSTRACT FROM AUTHOR]