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)

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)

Uses Software

• Algorithm 97