Algorithms for minimum-bend single row routing problem

The objective function of this problem is to minimize the number of doglegs (or bends) per net. The problem is of critical interest in the design of high-performance multilayer printed circuit boards; it also finds application in over-the-cell routing and design of microwave ICs. The approach is based on a graph theoretic representation in which an instance of the single row routing problem is represented by three graphs-an overlay graph, a containment graph, and an interval graph. Using this graph representation, three algorithms for the minimum-bend single row routing problem are developed. It is shown that the algorithms have very tight performance bounds. In particular, it is proved that the maximum number of doglegs per net is bounded by O (k), where k is the size of the maximum clique in a certain graph representing the problem