Technical Report No. 19, March 1990 - Abstract

Peter Widmayer:
On Shortest Paths in VLSI design

This report is not available in electronic form!

In physical VLSI design, network design (wiring) is the most time consuming phase. For solving global wiring problems, we propose to first compute form the layout geometry a graph that preserves all shortest paths between pairs of relevant points, and then to operate on that graph for computing shortest paths, Steiner minimal tree approximations, or the like. For a set of points and a set of simple orthogonal polygons as obstacles in the plane, with n input points (polygon corner or other) altogether, we show how a shortest paths preserving graph of size O(n*log n) can be computed in time O(n*log n) in the worst case, with space O(n). We illustrate the merits of this approach with a simple example: If the length of a longest edge in the graph is bounded by a polynomial in n, an assumption that is clearly fulfilled for graphs derived from VLSI layout geometries, then a shortest path can be computed in time O(n*log n*log(log n)) in the worst case; this result improves on the known best one of O(n*(log n)^(3/2)).