Multiple-source shortest paths in planar graphs

ABSTRACT

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.

REFERENCES

• 1: S. Alstrup, J. Holm, K. de Lichtenberg, M. Thorup, "Maintaining information in fully-dynamic trees with top trees," ArXiv cs.DS/0310065.
• 2: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 3: David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook, Maintenance of a minimum spanning forest in a dynamic plane graph, Journal of Algorithms, v.13 n.1, p.33-54, March 1992 [doi>10.1016/0196-6774(92)90004-V]
• 4: J. Fakcharoenphol, Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.232, October 14-17, 2001
• 5: 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]
• 6: Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991 [doi>10.1145/102782.102788]
• 7: Greg N. Frederickson, Using cellular graph embeddings in solving all pairs shortest paths problems, Journal of Algorithms, v.19 n.1, p.45-85, July 1995 [doi>10.1006/jagm.1995.1027]
• 8: 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]
• 9: R. Hassin, "Maximum flows in (s,t) planar networks," Inform. Process. Lett. 13 (1981), pp. 107.
• 10: Samir Khuller , Joseph Seffi Naor , Philip Klein, The lattice structure of flow in planar graphs, SIAM Journal on Discrete Mathematics, v.6 n.3, p.477-490, Aug. 1993 [doi>10.1137/0406038]
• 11: R. J. Lipton and R. E. Tarjan, "A separator theorem for planar graphs," SIAM J. Appl. Math. 36 (1979), pp. 177--189.
• 12: K. Mehlhorn , S. Näher, Bounded ordered dictionaries in O(loglogN) time and O(n) space, Information Processing Letters, v.35 n.4, p.183-189, Aug. 1990 [doi>10.1016/0020-0190(90)90022-P]
• 13: Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
• 14: Heike Ripphausen-Lipa , Dorothea Wagner , Karsten Weihe, The Vertex-Disjoint Menger Problem in Planar Graphs, SIAM Journal on Computing, v.26 n.2, p.331-349, April 1997 [doi>10.1137/S0097539793253565]
• 15: Jeanette P. Schmidt, All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings, SIAM Journal on Computing, v.27 n.4, p.972-992, Aug. 1998 [doi>10.1137/S0097539795288489]
• 16: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 17: M. Thorup, Compact Oracles for Reachability and Approximate Distances in Planar Digraphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.242, October 14-17, 2001
• 18: P. van Emde Boas, "Preserving order in a forest in less than logarithmic time and linear space," IPL 6 (1977), pp. 80--82.
• 19: Karsten Weihe, Maximum (s,t)-flows in planar networks in O(|V| log |V|) time, Journal of Computer and System Sciences, v.55 n.3, p.454-475, Dec. 1997 [doi>10.1006/jcss.1997.1538]