Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

DOI10.1016/J.COMGEO.2012.01.016zbMATH Open1271.05031OpenAlexW1992608637MaRDI QIDQ359743FDOQ359743

Authors Christian Wulff-Nilsen 

Publication date 22 August 2013

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S092577211200048X

zbMATH Keywords

diameterplanar graphWiener indexdistance oracleshortest path distances

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Recommendations

• Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Approximate distance oracles for planar graphs with improved query time-space tradeoff

Cites work

• scientific article; zbMATH DE number 4137792 (Why is no real title available?)
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Computing the dilation of edge-augmented graphs in metric spaces
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

Cited in

(1)

• Title not available (Why is no real title available?)

This page was built for publication: Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

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