Rectilinear paths among rectilinear obstacles

Given a set of obstacles and two distinguished points in the plane the problem of finding a collision-free path subject to a certain optimization function is a fundamental problem that arises in many fields, such as motion planning in robotics, wire routing in VLSI and logistics in operations research. In this survey we emphasize its applications to VLSI design and limit ourselves to the rectilinear domain in which the goal path to be computed and the underlying obstacles are all rectilinearly oriented, i.e., the segments are either horizontal or vertical. We consider different routing environments, and various optimization criteria pertaining to VLSI design, and provide a survey of results that have been developed in the past, present current results and give open problems for future research.     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

Disjoint shortest paths in graphs

It is an interesting problem that how much connectivity ensures the existence ofn disjoint paths joining givenn pairs of vertices, but to get a sharp bound seems to be very difficult. In this paper, we study how muchgeodetic connectivity ensures the existence ofn disjointgeodesics joining givenn pairs of vertices, where a graph is calledk-geodetically connected if the removal of anyk−1 vertices does not change the distance between any remaining vertices.     

An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model

In this paper, we present a direct approach for routing a shortest rectilinear path between two points among a set of rectilinear obstacles in a two-layer interconnection model that is used for VLSI routing applications. The previously best known direct approach for this problem takes O(nlog²n) time and O(nlogn) space, where n is the total number of obstacle edges. By using integer data structures and an implicit graph representation scheme (i.e., a generalization of the distance table method), we improve the time bound to O(nlog^3/2n) while still maintaining the O(nlogn) space bound. Comparing with the indirect approach for this problem, our algorithm is simpler to implement and is probably faster for a quite large range of input sizes.     

Reconfiguration graphs of shortest paths

For a graph $G$ and$a,b\in V\left(G\right)$, the shortest path reconfiguration graph of $G$ with respect to $a$ and$b$ is denoted by $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths between $a$ and$b$ in $G$. Two vertices in $V\left(S(G,a,b)\right)$ are adjacent, if their corresponding paths in $G$ differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.     

Visibility graphs and obstacle-avoiding shortest paths

Summary Two closely related problems in Computational Geometry are determining visibility graphs and shortest paths in a two- or three-dimensional environment containing obstacles. Applications are within Computer Graphics and Robotics. We give a survey on recent research done on efficient algorithms for these problems.

---

Zusammenfassung Zwei eng miteinander verwandte Probleme in der algorithmischen Geometrie sind die Bestimmung von Sichtbarkeitsgraphen und kürzesten Wegen in einer zwei- oder dreidimensionalen Umgebung mit Hindernissen. Anwendungen finden sich insbesondere auf den Gebieten Computergrafik und Robotik. Diese Arbeit gibt einen Überblick über kürzlich erschienene Arbeiten zum Entwurf effizienter Algorithmen für diese Probleme.

     

Rectilinear shortest paths in the presence of rectangular barriers

In this paper we address the following shortest-path problem. Given a point in the plane andn disjoint isothetic rectangles (barriers), we want to construct a shortestL ₁ path (not crossing any of the barriers) from the source point to any given query point. A restricted version of this problem (where the source and destination points are knowna priori) had been solved earlier inO(n ²) time. Our approach consists of preprocessing the source point and the barriers to obtain a planar subdivision where a query point can be located and a shortest path connecting it to the source point quickly transvered. By showing that any such path is monotone in at least one ofx ory directions, we are able to apply a plane sweep technique to divide the plane intoO(n) rectangular regions. This leads to an algorithm whose complexity isO(n logn) preprocessing time,O(n) space, andO(logn+k) query time, wherek is the number of turns on the reported path. If only the length of the path is sought,O(logn) query time suffices. Furthermore, we show an (n logn) time lower bound for the case where the source and destination points are known in advance, which implies the optimality of our algorithm in this case.A preliminary version of this paper appeared in theProceedings of the First Symposium on Computational Geometry (1985).Supported in part by CNPq-Conselho Nacional de Desenvolvimento Científico e Tecnológico (Brazil).Supported in part by the National Science Foundation under Grants MCS 8420814 and ECS 8340031.     

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

On finding shortest paths in nonnegative networks

A modification of Dantzig's algorithm for the all pairs shortest paths problem is given. The new algorithm applies only to graphs with nonnegative arc lengths. For an N-node complete graph it has a worst case running time of $\text{2}\text{3}\text{N}{}^3$ triple operations of the form D_ij: = min(D_ij, D_ik + D_kj) and N² log N other comparisons. This contrasts with a lower bound of N(N ? 1) (N ? 2) triples in any pure triple operation algorithm, and seems to be the first algorithm in which no operation need be repeated N³ times. Sparsity and some other conditions may also be utilized.     

On shortest cocycle covers of graphs

A cocycle (resp. cycle) cover of a graph G is a family C of cocycles (resp. cycles) of G such that each edge of G belongs to at least one member of C. The length of C is the sum of the cardinalities of its members. While it is known (see [5, 6]) that every bridgeless graph G = (V, E) has a cycle cover of length not greater than $\text{5}\text{3}\text{|E|}$, it is shown that there exists no α < 2 such that every loopless graph G = (V, E) has a cocycle cover with length not greater than α |E|. To do this, cocycle covers of minimal length are determined for the complete graphs, thus solving a problem stated at the end of [6].     

On an instance of the inverse shortest paths problem

The inverse shortest paths problem in a graph is considered, that is, the problem of recovering the arc costs given some information about the shortest paths in the graph. The problem is first motivated by some practical examples arising from applications. An algorithm based on the Goldfarb-Idnani method for convex quadratic programming is then proposed and analyzed for one of the instances of the problem. Preliminary numerical results are reported.     

On rectilinear duals for vertex-weighted plane graphs

Let G=(V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of G is a partition of a rectangle into |V| simple rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in E. A rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant. Furthermore, such a rectilinear cartogram can be constructed in O(nlogn) time where n=|V|.     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

Disjoint paths in a rectilinear grid

We give a good characterization and a good algorithm for a special case of the integral multicommodity flow problem when the graph is defined by a rectangle on a rectilinear grid. The problem was raised by engineers motivated by some basic questions of constructing printed circuit boards.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

On topological diversity of rectilinear representations of countably infinite graphs

We prove that, for each simple graph G whose set of vertices is countably infinite, there is a family ${\varvec{\mathcal{R}}(\varvec{G})}$ of the cardinality of the continuum of graphs such that (1) each graph ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ is isomorphic to G, all vertices of H are points of the Euclidean space E ³, all edges of H are straight line segments (the ends of each edge are the vertices joined by it), the intersection of any two edges of H is either their common vertex or empty, and any isolated vertex of H does not belong to any edge of H; (2) all sets ${\varvec{\mathcal{B}}(\varvec{H})}$ ( ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ ), where ${\varvec{\mathcal{B}}(\varvec{H})\subset \mathbf{E}^3}$ is the union of all vertices and all edges of H, are pairwise not homeomorphic; moreover, for any graphs ${\varvec{H}_1 \in \varvec{\mathcal{R}}(\varvec{G})}$ and ${\varvec{H}_2 \in \varvec{\mathcal{R}}(\varvec{G})}$ , ${\varvec{H}_1 \ne \varvec{H}_2}$ , and for any finite subsets ${\varvec{S}_i \subset \varvec{\mathcal{B}}(\varvec{H}_i)}$ (i = 1, 2), the sets ${\varvec{\mathcal{B}}(\varvec{H}_1){\setminus} \varvec{S}_1}$ and ${\varvec{\mathcal{B}}(\varvec{H}_2){\setminus} \varvec{S}_2}$ are not homeomorphic.     

On the weights of simple paths in weighted complete graphs

Consider a weighted simple graph G on the vertex set {1,..., n}. For any path p in G, we call ω _G (p) the sum of the weights of the edges of the path, and, for any {i, j} ? {1,..., n}, we define the multiset $$D_{\{ i,j\} } (G) = \left\{ {\left. {w_G \left( p \right)} \right|p a simple path between i and j} \right\}.$$ We establish a criterion for a multisubset of ? to be of the form $\mathcal{D}_{\{ i,j\} } (G)$ for some weighted complete graph G and for some i, j vertices of G. Besides we establish a criterion for a family of multi-subsets of ? to be of the form for some weighted complete graph G with vertex set {1,..., n}.