Oracles for bounded-length shortest paths in planar graphs
Authors:
Open Access
- 1 July 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 2 (3) , 335-363
Abstract
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 = ( V , E ), one can build in O(|V|) 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.Keywords
This publication has 16 references indexed in Scilit:
- Subgraph Isomorphism in Planar Graphs and Related ProblemsJournal of Graph Algorithms and Applications, 1999
- Finding and counting given length cyclesAlgorithmica, 1997
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning TreesSIAM Journal on Computing, 1997
- Planar orientations with low out-degree and compaction of adjacency matricesTheoretical Computer Science, 1991
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- Finding short cycles in planar graphs using separatorsJournal of Algorithms, 1986
- Arboricity and Subgraph Listing AlgorithmsSIAM Journal on Computing, 1985
- The clique problem for planar graphsInformation Processing Letters, 1981
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Homomorphies tze f r GraphenMathematische Annalen, 1968