The automated design of multilayer printed circuit boards is of great importance in the physical design of complex electronic systems. Wire routing is a crucial step in the design process. In this paper, the single row routing problem is considered. First, we discuss the relevance of single row routing in the context of the general routing problem. Then, we show that relaxing the restriction that backward moves are not allowed can result in smaller street congestions when there are at least four tracks in each street. Next, we obtain an O((2k)!kn log k) algorithm to determine whether or not an instance involving n nodes can be laid out (without backward moves) when only k tracks per street are available. With the additional restriction that wires are not permitted to cross streets, an efficient (O(n2)) algorithm is obtained. This restricted problem is shown to be related to a furnace assignment problem.

The single row approach represents a systematic suboptimal approach to the general multilayer rectilinear wire problem. With this approach, the single row wiring problem (i.e., one where all the points are collinear) forms the backbone of the general multilayer wiring problem. We consider the problem of generating minimum width layout for single row wiring problems. Our algorithm, which is not grid-based, is enumerative and uses a strong bounding criterion.