Abstract
We provide here efficient sequential and parallel solutions to the following problem: given a planar digraph G (with real edge weights but no negative cycles) for preprocessing, answer on-line queries requesting the shortest distance (or path) between any two vertices in G. Our algorithms for preprocessing need O(n log n + q 2) space and O(n log n + q 2) sequential time. (Here q is the cardinality of a set of faces of a planar embedding of G that cover all vertices.)A parallel implementation on a CREW PRAM needs also O(n log n + q 2) space and runs in O(log2 n) time using O(n + M(q)) processors (where M(q) is the number of processors required to multiply two q × q matrices in O(log q) time), provided that the q faces are given by the input.This enables us to achieve O(log n) time using a single processor for a “distance” query, or O(L + log n) time for a “path” query (where L is the length of the path). Note that this is a considerable improvement over previous results in the case where q = o(n). Our techniques are based on the hammock decomposition of a planar digraph and the use of separators for computing quickly internal distances in the graph. Several other results are achieved. For outerplanar graphs, our algorithms preprocess the graph in O(n logn) space and run either in O(n log n) sequential time, or in O(log2 n) time using O(n) processors on a CREW PRAM. A “distance” query can be answered in O(log n) time using a single processor. A “path” query is answered in O(L + log n) time. An optimal solution is given in the case of trees. We achieve O(1) time per “distance” query andwe need O(n) sequential time, or O(log n) time and O(n/log n) processors (on an EREW PRAM) for preprocessing. A “path” query is answered in O(L) time.
This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM), by the Ministry of Education of Greece and by a bilateral scientific agreement between Bulgaria and Greece.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Ausiello, G.F. Italiano, A.M. Spaccamela, U. Nanni, “Incremental algorithms for minimal length paths”, Proc. of ACM-SIAM SODA, 1990, pp.12–21.
D. Beinstock, C.L. Monma, “On the complexity of covering faces by vertices in a planar graph”, SIAM J. Comp., Vol.17, No.1, Feb. 1988, pp.53–76.
B. Berger, J. Rompel, P.W. Shor, “Efficient NC-algorithms for set cover with applications to learning and geometry”, Proc. 30th IEEE Symp. on FOCS, 1989, pp.54–59.
H. Djidjev, G. Pantziou, C. Zaroliagis, “Computing Shortest Paths and Distances in Planar Graphs”, CTI TR-90.10.26, Computer Technology Institute, Patras, October 1990.
G.N. Frederickson, “Fast Algorithms for Shortest Paths in Planar Graphs with Applications”, SIAM J. Comp., Vol.16, 1987, pp.1004–1022.
G.N. Frederickson, “Planar Graph Decomposition and All Pairs Shortest Paths”, TR-89-015, ICSI, Berkeley, March 1989. A preliminary version was appeared as “A new approach to all pairs shortest paths in planar graphs”, Proc. 19th ACM STOC, New York City, May 1987, pp.19–28.
G.N. Frederickson “Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems”, CSD-TR-897, Purdue University, August 1989. A preliminary version was appeared in Proc. 30th IEEE Symp. on FOCS, 1989, pp.448–453.
G.N. Frederickson, R. Janardan, “Designing Networks with Compact Routing Tables”, Algorithmica, 3 (1988), pp.171–190.
M.L. Fredman, R.E. Tarjan, “Fibonacci heaps and their use in improved network optimization algorithms”, J. ACM, 34(1987), pp.596–615.
D. Knuth, “The Art of Computer Programming”, Vol.1, Fundamental Algorithms, 2nd ed. Addison-Wesley, 1973.
A. Lingas, “Efficient parallel algorithms for path problems in planar directed graphs”, Proc. of SIGAL90, LNCS, Vol.450, pp. 447–457.
G. Pantziou, P. Spirakis, C. Zaroliagis, “Efficient Parallel Algorithms for Shortest Paths in Planar Graphs”, CTI TR-90.01.02, Computer Technology Institute, Patras, September 1990 (revised version). A preliminary version has appeared as Proc. of the 2nd Scand. Workshop on Algorithm Theory (SWAT90), Bergen, Norway, 11–14 July, 1990, LNCS, Vol. 447, pp.288–300, Springer-Verlag.
B. Schieber, U. Vishkin, “On finding lowest common ancestors: simplification and parallelization”, Proc. 3rd AWOC88, Corfu, Greece, July 1988, LNCS Vol. 319 (ed. J.H. Reif), pp.111–123, Springer-Verlag.
R.E. Tarjan, U. Vishkin, “An efficient parallel biconnectivity algorithm”, SIAM J. Comp., 14 (1985), pp. 862–874.
J. van Leeuwen, R.B. Tan, “Computer Networks with compact routing tables”, in The Book of L, G. Rozenberg and A. Salomaa (eds.), Springer-Verlag, New York (1986), pp.259–273.
J.C. Wyllie, “The Complexity of Parallel Computation”, PhD Thesis, TR 79-387, Dept of Computer Science, Cornell University, Ithaca, NY, 1979.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Djidjev, H.N., Pantziou, G.E., Zaroliagis, C.D. (1991). Computing shortest paths and distances in planar graphs. In: Albert, J.L., Monien, B., Artalejo, M.R. (eds) Automata, Languages and Programming. ICALP 1991. Lecture Notes in Computer Science, vol 510. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54233-7_145
Download citation
DOI: https://doi.org/10.1007/3-540-54233-7_145
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54233-9
Online ISBN: 978-3-540-47516-3
eBook Packages: Springer Book Archive