Almost optimal distance oracles for planar graphs

DOI10.1145/3313276.3316316zbMath1433.68284arXiv1811.01551OpenAlexW2962711627MaRDI QIDQ5212755

Panagiotis Charalampopoulos, Oren Weimann, Paweł Gawrychowski, Shay Mozes

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsshortest pathsVoronoi diagramsdistance oracles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items

Better distance labeling for unweighted planar graphs, Finding top-\(k\) longest palindromes in substrings, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Better distance labeling for unweighted planar graphs, Shortest-Path Queries in Geometric Networks, Fault-tolerant distance labeling for planar graphs, An efficient oracle for counting shortest paths in planar graphs, Single-source shortest paths and strong connectivity in dynamic planar graphs, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Fault-tolerant distance labeling for planar graphs, An efficient oracle for counting shortest paths in planar graphs