NEW THREE-LAYER DETAILED ROUTER FOR VLSI LAYOUT.

A three-layer detailed router that is capable of routing a rectilinear wiring area containing obstacles such as prerouted pins is presented. It supports pins fixed on all sides of the area. A routing methodology is developed; it is basically a divide-and-conquer that partitions the routing area into subones by specially chosen cut lines and then uses a concurrently bidirectional column scanning approach to route each subregion. In each column, a signal column maze router with backtracking is developed. This router consistently outperforms several known routers in quality of wiring.