Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

DOI10.1145/3218821MaRDI QIDQ4629989zbMATH OpenOpenAlexWikidataFDO

Authors S. Cabello

Publication date 28 March 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.07815

zbMATH Keywords

diameterplanar graphVoronoi diagramWiener indexdistances in graphsdistance counting

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Abstract: We show how to compute for $n$-vertex planar graphs in $O(n^{11/6}mpolylog(n))$ expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In $O(n^{15/8}mpolylog(n))$ expected time we can also compute the number of pairs of vertices at distance smaller than a given threshold. These are the first algorithms for these problems using time $O(n^c)$ for some constant $c<2$, even when restricted to undirected, unweighted planar graphs.

Recommendations

• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Many distances in planar graphs
• Approximating the diameter of planar graphs in near linear time
• Faster approximate diameter and distance oracles in planar graphs

Cited in

(36)

• Better distance labeling for unweighted planar graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• The complexity of diameter on H-free graphs
• Obstructions to faster diameter computation: asteroidal sets
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• The complexity of diameter on \(H\)-free graphs
• Improved outerplanarity bounds for planar graphs
• _i-metric graphs: radius, diameter and all eccentricities
• A story of diameter, radius, and (almost) Helly property
• Continuous mean distance of a weighted graph
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Better distance labeling for unweighted planar graphs
• Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Almost optimal exact distance oracles for planar graphs
• Compact distributed certification of planar graphs
• The diameter of AT‐free graphs
• Parameterized complexity of streaming diameter and connectivity problems
• Approximating the Diameter of Planar Graphs in Near Linear Time
• An almost optimal edit distance oracle
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Computing and Combinatorics
• Eccentricity queries and beyond using hub labels
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
• Beyond Helly graphs: the diameter problem on absolute retracts
• Distributed planar reachability in nearly optimal time
• Distance problems within Helly graphs and \(k\)-Helly graphs
• Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Approximating the diameter of planar graphs in near linear time
• Maximal distortion of geodesic diameters in polygonal domains
• Parameterized complexity of streaming diameter and connectivity problems
• Medians in median graphs and their cube complexes in linear time

This page was built for publication: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629989)