In this paper an O(NlogN) algorithm for routing through a rectangle is presented. Consider an n-by-m rectangular grid and a set of N two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in O(NlogN) time; this contrasts favorably with the area of the layout that might be as large as N2. The layout constructed can be wired using four layers of interconnect with only O(N) contact cuts. A partial extension to multiterminal nets is also discussed.:9l
--Authors’ Abstract
This paper is an important contribution to VLSI design, reducing the time requirement for rectangle routing by an order of magnitude (the previous best rectangle routing algorithm was O(nm), and expressing the time complexity entirely in terms of the number of nets rather than in terms of rectangle size.
As the abstract indicates, the problem treated in this paper is easy to state. Unfortunately, as often happens in computer science, it is, at the same time, hard to solve. The paper is well and clearly written, with few typos, but it is nevertheless complex and difficult to read. (As a measure of this complexity, the first six pages contain 35 definitions embedded in nontrivial introductory material.) It will be of considerable interest to specialists in this aspect of VLSI design, and to some graph theorists. However, it will not be easily accessible to most computer professionals.
