Optimal Rotation Problems in Channel Routing

In the channel routing problem, a problem arising in the design of layout systems, two rows of terminals which are opposite each other, have to be connected. We study what effect the rotation of one row of terminals has on the cost measures of the routing phase. The cost measures we consider are the density, which is proportional to the width of the channel, the crossing number, which is closely related to the number of crossings between two wires in the channel, and the length of nets, which is related to the wire length needed in the routing. We present algorithms for determining the rotations which minimize each of these cost measures. The algorithms can also be used for solving optimal offset problems.