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

diameterdistance countingdistances in graphsplanar graphVoronoi diagramWiener index

Mathematics Subject Classification ID

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

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

(41)

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

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)