### 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))*.