We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation @math , we show how to construct in @math time a data structure of size @math that answers distance queries in @math time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever @math . * We provide a linear-space exact distance oracle for planar graphs with query time @math for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space @math such that for any pair of nodes at distance D the query time is @math . Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with @math nodes, we can preprocess G in @math time to produce a data structure of size @math that can answer the following queries in @math time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA'05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For @math and space @math , we essentially improve the query time from @math to @math .
Efficient data structures for shortest-path queries have also been devised for restricted classes of planar graphs @cite_37 @cite_57 and for restricted types of queries @cite_29 @cite_50 @cite_6 @cite_17 . If approximate distances and shortest paths are sufficient, a better tradeoff with @math space and @math query time has been achieved @cite_48 @cite_26 @cite_17 @cite_32 .
@cite_37 @cite_26 @cite_48 @cite_29 @cite_32 @cite_6 @cite_57 @cite_50 @cite_17
2094724468 2003457914 2096304547 2092904196 1623319572 2060296641 1985248597 2068243119 2078443814
We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n -vertex digraphs of genus O(n 1-e ) for any e>0 . We describe a method for preprocessing a weighted planar undirected graph and representing the results of the preprocessing so as to facilitate subsequent approximate distance queries. For any 0 2 n distances. By using compressed representation of the distances, the number of bytes required is about .5ne-1(9 + 3 log e-1)log 2 n (at the expense of a small increase in query time). It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an O(log n) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only.The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from 0, …, N , it approximates distances within a factor (1 + e) in O(log log (nN) + 1 e) time. Our scheme can be extended to find and route along correspondingly short dipaths. A (1+e)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM'04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC'06). However, these require Ω(e-1n lg n) space for n-node graphs. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of e and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(nlg2 n). However, our constructions have slower query times. For planar graphs, the query time is O(e-2 lg2 n). For all our linear-space results, we can in fact ensure, for any δ > 0, that the space required is only 1 + δ times the space required just to represent the graph itself. Weighted paths in directed grid graphs of dimension (m X n) can be used to model the string edit problem, which consists of obtaining optimal (weighted) alignments between substrings of A, |A|=m, and substrings of B, |B|=n. We build a data structure (in O(mn log m) time) that supports O(log m) time queries about the weight of any of the O(m2n) best paths from the vertices in column 0 of the graph to all other vertices. Using these techniques we present a simple O(n2 log n) time and @math space algorithm to find all (the locally optimal) approximate tandem (or nontandem) repeats xy within a string of size n. This improves (by a factor of log n) upon several previous algorithms for this problem and is the first algorithm to find all locally optimal repeats. For edit graphs with weights in 0, -1, 1 , a slight modification of our techniques yields an O(n2) algorithm for the cyclic string comparison problem, as compared to O(n2 log n) for the case of general weights. The problem of processing shortest pa th queries in graphs arises in application areas such as intelligent t ranspor ta t ion system (ITS), geographic information system (GIS), and robotics. In this paper, we present an efficient algorithmic solution for processing shortest pa th queries in undirected planar graphs with non-negative edge weights. Previous algorithms for this problem on planar graphs all have a tradeoff between the query t ime and the da ta structure space used by the solutions. The previously best known trade-off on an n-vertex planar graph G in the worst case is O(v -r) t ime for a pa th length query and O(v -r + L) t ime for report ing an actual shortest path, with a da ta structure of O(n2 x ) space, where r is an integer parameter with 1 < r _< n and L is the number of edges on the output shortest path. We present a new scheme, called frame search, that exploits the graph planari ty in a novel fashion. Wi th this scheme, we build an improved da ta structure of O(n + pv -r + p2 r) space (in O(n + p2 v + pr 3 4) time), where p is the minimum cardinality of a face-covering of the planar embedding of G with 1 < p < O(n), and r is an integer parameter with 1 < r < p. This da ta structure enables us to process each length query in O(v -rlog r + a(n)) t ime and report an actual shortest path in an addit ional O(L) time, where a(n) is the inverse of Ackermann's function. In the worst case, our approach reduces the previously best query t ime by a factor of up to O(n 1 4) if the same amount of space is used. Our technique can also be applied to improve the previous query algorithms for some geometric shortest pa th problems on the plane. We present a new approach for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G e (V, E), one can build in O(vVv) time a data structure, which allows to check in O(1) time whether two given vertices are at distance at most k in G and if so a shortest path between them is returned. Graph G can be undirected as well as directed.Our data structure works in fully dynamic environment. It can be updated in O(1) time after removing an edge or a vertex while updating after an edge insertion takes polylogarithmic amortized time. Besides deleting elements one can also disable ones for some time. It is motivated by a practical situation where nodes or links of a network may be temporarily out of service.Our results can be easily generalized to other wide classes of graphs---for instance we can take any minor-closed family of graphs. Given an n-node planar graph with nonnegative edge-lengths, our algorithm takes O(n log n) time to construct a data structure that supports queries of the following form in O(log n) time: given a destination node t on the boundary of the infinite face, and given a start node s anywhere, find the s-to-t distance.