A Line-Expansion Algorithm for the General Routing Problem with a Guaranteed Solution

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.