Area-optimal three-layer channel routing

The channel routing problem in the knock-knee mode is considered. The algorithm presented always constructs a correct layout in a channel of bounded size, if there is one, and guarantees that it is wirable with only three conducting layers; that is, the layout is optimal with respect to the area and to the number of layers. The algorithm thus improves all previously known layout algorithms, which either use additional columns to produce a three-layer wirable layout or construct a layout for which the three-layer wirability is not proved. For the layer assignment only O(N) (N is the number of nets) vias are used. The algorithm can be implemented to run in O (N log N) time