On graphs preserving rectilinear shortest paths in the presence of obstacles

In physical VLSI design, network design (wiring) is the most time-consuming phase. For solving global wiring problems, it is proposed to first compute from 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, it is shown how a shortest paths preserving graph of size O(nlogn) can be computed in time O(nlogn) in the worst case, with space O(n). The paper illustrates 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(nlognloglogn) in the worst case; this result improves on the known best one of O(n(logn)³’/²).