In recent Printed Circuit Boards (PCB), the design size and density have increased, and the improvement of routing tools for PCB is required. There are several routing tools which generate high quality routing patterns when connection requirement can be realized by horizontal and vertical segments only. However, in high density PCB, the connection requirements cannot be realized when only horizontal and vertical segments are used. Up to one third nets can not be realized if no non-orthogonal segments are used. In this paper, a routing method for a single-layer routing area that handles higher density designs in which 45-degree segments are used locally to relax the routing density is introduced. In the proposed method, critical zones in which non-orthogonal segments are required in order to realize the connection requirements are extracted, and 45-degree segments are used only in these zones. By extracting minimal critical zones, the other area that can be used to improve the quality of routing pattern without worry about connectivity issues is maximized. Our proposed method can utilize the routing methods which generate high quality routing pattern even if they only handle horizontal and vertical segments as subroutines. Experiments show that the proposed method analyzes a routing problem properly, and that the routing is realized by using 45-degree segments effectively.

This paper presents a three layer over-the-cell (OTC) routing algorithm for standard cells with nonuniform OTC routing capacities in standard cell design. Since the number of available routing tracks on the second metal layer of OTC varies column by column, the proposed OTC routing method can effectively utilize the OTC regions. The proposed router performs two types of OTC routing. For the OTC regions near the channel, it performs planar routing. For the OTC regions far from the channel, it performs H-V routing on the second and third layers. Combining planar and H-V routings, the router can utilize the OTC effectively, that could hardly be achieved by existing algorithms. We also formulate the problem of selecting planar routable nets on the third layer as the maximum weighted planar routable net selection problem with nonuniform routing capacity, and propose an optimal algorithm. Experimental results show that the proposed router produces small height layouts as compared to those produced by the routers based on the existing cell model with uniform OTC routing capacity.