A Linear-Time Routing Algorithm for Convex Grids
Takao Nishizeki, N. Saito, K. Suzuki · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1985
In this paper, we consider the channel routing problem involving two-terminal nets on rectilinear grids. An efficient algorithm is described which necessarily finds a routing in a given grid whenever it exists. The algorithm is not a heuristic but an exact one, and works for a rather large class of grids, called convex grids, including the grids of rectangular, T-, L-, or X-shape boundaries. Both the running time and required space are linear in the number of vertices of a grid.