A Topologically Based Non-Minimum Distance Routing Algorithm

In this paper, a unique topologically based non-minimum distance routing algorithm is presented. It offers both maximal completion rates and minimal via usage. The algorithm is based on a topological transformation of a significant subset of the PC routing problem: A broad channel encompassing a full row of DIPs and all routes within it. This transformation eliminates the need to consider detailed path shapes during routing. The routing problem is transformed into a permutation of nets. It is coupled with a backtrack search to produce a powerful routing algorithm. The search is conducted in a planar environment.