Short path queries in planar graphs in constant time

ABSTRACT

We present a new algorithm 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 distant by at most k in G and if so a shortest path between them is returned. This significantly improves the previous result of D. Eppstein [5] where after a linear preprocessing the queries are answered in O(log |V|) time. Our approach can be applied to compute the girth of a planar graph and a corresponding shortest cycle in O(|V|) time provided that the constant bound on the girth is known.Our results can be easily generalized to other wide classes of graphs~--~for instance we can take graphs embeddable in a surface of bounded genus or graphs of bounded tree-width.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Danny Z. Chen , Jinhui Xu, Shortest path queries in planar graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.469-478, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335359]
• 3: Marek Chrobak , David Eppstein, Planar orientations with low out-degree and compaction of adjacency matrices, Theoretical Computer Science, v.86 n.2, p.243-266, Sept. 2, 1991 [doi>10.1016/0304-3975(91)90020-3]
• 4: Hristo Djidjev, Computing the Girth of a Planar Graph, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.821-831, July 09-15, 2000
• 5: D. Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms & Applications, 3(3):1--27, 1999.
• 6: Greg N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM Journal on Computing, v.26 n.2, p.484-538, April 1997 [doi>10.1137/S0097539792226825]
• 7: G. Ramalingam , J. van Leeuwen , J. Hartmanis , G. Goos, Bounded Incremental Computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1996

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms

Keywords:
planar graph, queries, shortest path