The single-row single-layer routing is considered for net lists with density5 when backward moves are allowed. A heuristic routing algorithm is given and tested. Comparing with a conventional router, better realizations were found for 38% of randomly generated net lists.

Layering problem of multilayer printed wiring boards in the single-row routing approach is considered. For use in high density printed wiring boards, an extended layering algorithm is proposed for the case of street capacity K2, while all conventional algorithms are for K=2.

The cost trade-off between the number of additional vias employed and the number of layers decreased in Ref.(2) is discussed. We present a cost model and show that the technique in Ref.(2) really reduce the total cost for producing the board.

The single-row routing approach to the design of multilayer printed wiring boards decomposes the general problem into a number of independent phases. The layering phase is considered in this paper. We assume that the street capacity is exactly two in each layer. Recent advances in the technology of microelectronics, which enables us to produce high density boards, show that it is possible to drill one via between any two adjacent vertices on the single-row where at most two wire segments are passed. We call these vias as additional vias. We give a new upper bound to the number of layers while using additional vias is permitted. A polynomial time algorithm SPLIT is given for assigning nets to m layers where m is less than or equal to the new upper bound. The number of additional vias is not limited in algorithm SPLIT. For having a reasonable number of additional vias on the single-row, a heuristic algorithm LIMIT_SPLIT is proposed. LIMIT_SPLIT is implemented and compared with a related conventional algorithm. Experimental results show that LIMIT_SPLIT takes the shorter run time and provides smaller number of layers for 59% of the randomly generated net lists while using no more than two additional vias in each case.