Faster Approximate Diameter and Distance Oracles in Planar Graphs

DOI10.4230/LIPICS.ESA.2017.25MaRDI QIDQ5111711zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Dimitrios Skrepetos

Publication date 27 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7838/pdf/LIPIcs-ESA-2017-25.pdf/

zbMATH Keywords

diameterplanar graphsabstract Voronoi diagrams

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Recommendations

• Faster approximate diameter and distance oracles in planar graphs
• Fast and Compact Oracles for Approximate Distances in Planar Graphs
• Approximating the diameter of planar graphs in near linear time
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Approximate distance oracles for planar graphs with improved query time-space tradeoff
• Almost optimal distance oracles for planar graphs
• More compact oracles for approximate distances in undirected planar graphs
• Better tradeoffs for exact distance oracles in planar graphs

Cites work

• scientific article; zbMATH DE number 2119743 (Why is no real title available?)
• scientific article; zbMATH DE number 910922 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
• Approximating the diameter of planar graphs in near linear time
• Compact oracles for reachability and approximate distances in planar digraphs
• Computing the dilation of edge-augmented graphs in metric spaces
• Concrete and abstract Voronoi diagrams
• Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster Approximation of Distances in Graphs
• Faster shortest-path algorithms for planar graphs
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Maintaining information in fully dynamic trees with top trees
• More compact oracles for approximate distances in undirected planar graphs
• Multiple-source shortest paths in planar graphs
• Randomized incremental construction of abstract Voronoi diagrams
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time

Cited in

(11)

• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Almost optimal distance oracles for planar graphs
• scientific article; zbMATH DE number 2119743 (Why is no real title available?)
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Fast and Compact Oracles for Approximate Distances in Planar Graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• Faster approximate diameter and distance oracles in planar graphs
• Approximating the diameter of planar graphs in near linear time
• Planar diameter via metric compression

This page was built for publication: Faster Approximate Diameter and Distance Oracles in Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111711)