×
Wulff-Nilsen, Christian

Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time. (English) Zbl 1271.05031

Comput. Geom. 46, No. 7, 831-838 (2013).
Summary: Let \(G\) be an \(n\)-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the , defined as the sum of all-pairs shortest path distances, and the diameter of \(G\) can be computed in \(o(n^2)\) time. We show that both problems can be solved in \(O(n^2\log\log n/\log n)\) time with \(O(n)\) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in \(G\).
More generally, for any parameter \(S\in[(\log n/\log\log n)^2,n^{2/5}]\), distance queries can be answered in \(O(\sqrt{S}\log S/\log n)\) time per query with \(O(n^2/\sqrt{S})\) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when \(\log S= o(\log n)\). All algorithms have requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.
© Elsevier B.V.

MSC:

05C12 Distance in graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
68Q25 Analysis of algorithms and problem complexity
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)

Keywords:

planar graph; Wiener index; diameter; shortest path distances; distance oracle
Cite Review PDF
Full Text: DOI Link

References:

[1] Alon, N.; Seymour, P.; Thomas, R., A separator theorem for nonplanar graphs, J. Amer. Math. Soc., 3, 4, 801-808, 1990 · Zbl 0747.05051
[2] Cabello, S.; Knauer, C., Algorithms for graphs of bounded treewidth via orthogonal range searching, Comput. Geom., 42, 9, 815-824, 2009 · Zbl 1200.05218
[3] Chepoi, V.; Klavžar, S., The Wiener index and the Szeged index of benzenoid systems in linear time, J. Chem. Inf. Comput. Sci., 37, 752-755, 1997
[4] Chung, F. R.K., Diameters of graphs: old problems and new results, Congr. Numer., 60, 295-317, 1987 · Zbl 0695.05029
[5] Djidjev, H., Efficient algorithms for shortest path problems on planar digraphs, 151-165 · Zbl 1539.68219
[6] Frederickson, G. N., Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput., 16, 1004-1022, 1987 · Zbl 0654.68087
[7] Lipton, R. J.; Tarjan, R. E., A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 2, April 1979 · Zbl 0432.05022
[8] Wiener, H., Structural determination of paraffin boiling points, J. Amer. Chem. Soc., 69, 17-20, 1947
[9] C. Wulff-Nilsen, Algorithms for planar graphs and graphs in metric spaces, Ph.D. thesis, March 2010.
[10] Zmazek, B.; Žerovnik, J., Computing the weighted Wiener and Szeged number on weighted cactus graphs in linear time, Croatica Chemica Acta, 76, 137-143, 2003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.