Compact oracles for reachability and approximate distances in planar digraphs

ABSTRACT

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 + ϵ) in O(log log (nN) + 1/ϵ) time. Our scheme can be extended to find and route along correspondingly short dipaths.

REFERENCES

• 1: Srinivasa Rao Arikati , Danny Z. Chen , L. Paul Chew , Gautam Das , Michiel H. M. Smid , Christos D. Zaroliagis, Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane, Proceedings of the Fourth Annual European Symposium on Algorithms, p.514-528, September 25-27, 1996
• 2: Danny Z. Chen, On the all-pairs Euclidean short path problem, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.292-301, January 22-24, 1995, San Francisco, California, United States
• 3: 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]
• 4: Hristo Djidjev, On-Line Algorithms for Shortest Path Problems on Planar Digraphs, Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, p.151-165, June 12-14, 1996
• 5: Hristo N. Djidjev , Grammati E. Pantziou , Christos D. Zaroliagis, Computing shortest paths and distances in planar graphs, Proceedings of the 18th international colloquium on Automata, languages and programming, p.327-338, June 1991, Madrid, Spain
• 6: Hristo Djidjev , Grammati E. Pantziou , Christos D. Zaroliagis, Fast Algorithms for Maintaining Shortest Paths in Outerplanar and Planar Digraphs, Proceedings of the 10th International Symposium on Fundamentals of Computation Theory, p.191-200, August 22-25, 1995
• 7: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 8: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
• 9: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 10: A. Gupta , A. Kumar, Traveling with a Pez Dispenser (Or, Routing Issues in MPLS), Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.148, October 14-17, 2001
• 11: Anupam Gupta , Amit Kumar , Mikkel Thorup, Tree based MPLS routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777443]
• 12: Torben Hagerup , Peter Bro Miltersen , Rasmus Pagh, Deterministic dictionaries, Journal of Algorithms, v.41 n.1, p.69-85, October 2001 [doi>10.1006/jagm.2001.1171]
• 13: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 14: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 15: Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
• 16: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 17: Philip Klein, Preprocessing an undirected planar network to enable fast approximate distance queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.820-827, January 06-08, 2002, San Francisco, California
• 18: Klein, P., and Subramanian, S. 1998. A fully dynamic approximation scheme for shortest path problems in planar graphs. Algorithmica 23, 235--249.
• 19: Lipton, R., and Tarjan, R. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177--189.
• 20: David Peleg, Informative Labeling Schemes for Graphs, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, p.579-588, September 01, 2000
• 21: Peleg, D. 2000b. Proximity-preserving labeling schemes. J. Graph Theory 33, 167--176.
• 22: Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
• 23: Neil Robertson , P. D. Seymour, Graph minors. XVI. excluding a non-planar graph, Journal of Combinatorial Theory Series B, v.89 n.1, p.43-76, September 2003 [doi>10.1016/S0095-8956(03)00042-X]
• 24: Santoro, N., and Khatib, R. 1985. Labelling and implicit routing in networks. Comput. J. 28, 1, 5--8.
• 25: Sairam Subramanian, A Fully Dynamic Data Structure for Reachability in Planar Digraphs, Proceedings of the First Annual European Symposium on Algorithms, p.372-383, September 30-October 02, 1993
• 26: Roberto Tamassia , Ioannis G. Tollis, Dynamic reachability in planar digraphs with one source and one sink, Theoretical Computer Science, v.119 n.2, p.331-343, Oct. 25, 1993 [doi>10.1016/0304-3975(93)90164-O]
• 27: Thorup, M. 1995. Shortcutting planar digraphs. Combin., Prob. Comput. 4, 287--315.
• 28: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 29: Mikkel Thorup, On RAM Priority Queues, SIAM Journal on Computing, v.30 n.1, p.86-109, 2000 [doi>10.1137/S0097539795288246]
• 30: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 31: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 32: van Leeuwen, J., and Tan, R. 1986. Computer networks with compact routing tables. In The book of L, G. Rozenberg and A. Salomaa, Eds. Springer-Verlag, New York, 259--273.
• 33: Williams, J. 1964. Heapsort. Commun. ACM 7, 5, 347--348.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling; Path and circuit problems; Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Planar graphs, reachability and shortest paths oracles