Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

2017/02/25 by Sergio Cabello, Cabello, Sergio · 2 citations
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1702.07815

openalex publication_date 2017/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show how to compute for n-vertex planar graphs in O(n^11/6\rm polylog(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\rm polylog(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.

Cited by

• Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
• Going Beyond Surfaces in Diameter Approximation

Related

• Approximating the Diameter of Planar Graphs in Near Linear Time
• Going Beyond Surfaces in Diameter Approximation
• Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic O(n^5/3) time
• Algorithms for Distance Problems in Continuous Graphs