Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time

DOI10.1137/18M1193402MaRDI QIDQ5858646

Paweł Gawrychowski, Shay Mozes, Oren Weimann, Haim Kaplan, Micha Sharir

Publication date: 14 April 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1193402

zbMATH Keywords

diameter; shortest paths; planar graph; Voronoi diagrams; divide-and-conquer

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Parameterized complexity of diameter, Maximal distortion of geodesic diameters in polygonal domains

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On dynamic shortest paths problems
• Randomized incremental construction of abstract Voronoi diagrams
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Abstract Voronoi diagrams revisited
• An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• Geometric applications of a matrix-searching algorithm
• Computation of the center and diameter of outerplanar graphs
• Concrete and abstract Voronoi diagrams
• A new upper bound on the complexity of the all pairs shortest path problem
• Which problems have strongly exponential complexity?
• Applications of random sampling in computational geometry. II
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Efficient algorithms for center problems in cactus networks
• Improved algorithm for all pairs shortest paths
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Maintaining Minimum Spanning Forests in Dynamic Graphs
• Finding, Minimizing, and Counting Weighted Subgraphs
• Multiple-Source Shortest Paths in Embedded Graphs
• An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• COMPUTING THE MAXIMUM DETOUR OF A PLANE GEOMETRIC GRAPH IN SUBQUADRATIC TIME
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• A simple linear-time algorithm for computing the center of an interval graph
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Shortest Cut Graph of a Surface with Prescribed Vertex Set
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A more efficient algorithm for the min-plus multiplication
• New Bounds on the Complexity of the Shortest Path Problem
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Matrix Searching with the Shortest-Path Metric
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Tight Hardness Results for Maximum Weight Rectangles
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Computing Graph Distances Parameterized by Treewidth and Diameter
• Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
• Almost optimal distance oracles for planar graphs
• Holiest minimum-cost paths and flows in surface graphs
• Faster all-pairs shortest paths via circuit complexity
• Exact Weight Subgraphs and the k-Sum Conjecture
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Structured recursive separator decompositions for planar graphs in linear time
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Algorithms and Computation
• A Theorem on Boolean Matrices
• Faster shortest-path algorithms for planar graphs