Faster approximate diameter and distance oracles in planar graphs

DOI10.1007/s00453-019-00570-zzbMath1425.68454OpenAlexW2939467540MaRDI QIDQ1999961

Dimitrios Skrepetos, Timothy M. Chan

Publication date: 27 June 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7838/

zbMATH Keywords

diameterplanar graphsshortest pathsapproximation algorithmsVoronoi diagramsdistance oracles

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 (3)

Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Shortest-Path Queries in Geometric Networks ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs

Cites Work

• Randomized incremental construction of abstract Voronoi diagrams
• How to draw a planar graph on a grid
• Computing the dilation of edge-augmented graphs in metric spaces
• Making data structures persistent
• Concrete and abstract Voronoi diagrams
• Surpassing the information theoretic bound with fusion trees
• Applications of random sampling in computational geometry. II
• A data structure for dynamic trees
• 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
• 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
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Improved sparse covers for graphs excluding a fixed minor
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Faster approximate diameter and distance oracles in planar graphs