A line-expansion algorithm for the general routing problem with a guaranteed solution

ABSTRACT

A new routing algorithm is presented which is based on the expansion of a line in the direction perpendicular to the line. The line-expansion principle is first applied to the single layer routing problem. For the routing on two layers only some minor modifications have to be made. An important extension is added in which the search for an interconnection from a given point is initiated in more than one direction at the same time. The major advantage of the line-expansion algorithm over the well-known line-search algorithm is the guarantee that always a solution will be found if one exists.

REFERENCES

• 1: W. SANSEN, R. GOVAERTS, W. HEYNS, H. BEKE, May 1980, "Minicomputer Interactive System for Hybrid Automation", Proceedings 1st International Hybrid Microelectronics Conference, Japan.
• 2: LEE, C.Y., September 1961, "An algorithm for path connections and its applications", IEEE transactions on electronic computers, pp. 346-365.
• 3: Pratima Agarwal , M. A. Breuer, Some theoretical aspects of algorithmic routing, Proceedings of the 14th conference on Design automation, p.23-31, January 1977
• 4: MIKAMI, K., TABUCHI, K., 1969 "A computer program for optimal routing of printed circuit conductors", Proceedings Information Processing '68, North -Holland Publishing, pp. 1475-1478.
• 5: J. Soukup, Fast maze router, Proceedings of the 15th conference on Design automation, p.100-102, June 19-21, 1978, Las Vegas, Nevada, United States
• 6: J. Soukup, Global router, Proceedings of the 16th Conference on Design automation, p.481-484, June 25-27, 1979, San Diego, CA, United States
• 7: Lawrence Dysart , Mikhail Koifman, An application of branch and bound method to automatic printed circuit board routing, Proceedings of the 16th Conference on Design automation, p.494-499, June 25-27, 1979, San Diego, CA, United States
• 8: David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
• 9: Ivan Dobes, A multi-contouring algorithm, Proceedings of the 14th conference on Design automation, p.12, January 1977

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory