Faster Approximate Diameter and Distance Oracles in Planar Graphs

DOI10.4230/LIPIcs.ESA.2017.25zbMath1442.68262OpenAlexW2759043819MaRDI QIDQ5111711

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

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

Related Items

Faster approximate diameter and distance oracles in planar graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized incremental construction of abstract Voronoi diagrams
• Computing the dilation of edge-augmented graphs in metric spaces
• Concrete and abstract Voronoi diagrams
• Maintaining information in fully dynamic trees with top trees
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
• All-pairs shortest paths for unweighted undirected graphs in o ( mn ) time
• Fast Algorithms for Finding Nearest Common Ancestors
• Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
• Faster Approximation of Distances in Graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Compact oracles for reachability and approximate distances in planar digraphs
• More Compact Oracles for Approximate Distances in Undirected Planar Graphs
• Faster shortest-path algorithms for planar graphs