Content area
Abstract
In this thesis, we present a completely new approach to the classical single row routing problem. 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 overlap graph, a containment graph and an interval graph. Three decomposition schemes for a single row routing problem are developed, based on connectivity properties of these graphs. We also investigate the conditions under which optimal composition is possible. For several special classes of the single row routing problem optimal algorithms are developed. These results lead to an efficient heuristic for solving the single row routing problem. In addition, we investigate neccessary and sufficient conditions for a layout with bounded number of doglegs per net.
Our approach is significantly different from all previous approaches in the sense that it is based entirely on the graph-theoretic properties of the routing configuration and does not involve layout explicitly. The approach also leads to many interesting theoretical insights into the single row routing problem.
