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

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

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)

Cites Work

• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Title not available (Why is that?)
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Computing the dilation of edge-augmented graphs in metric spaces
• Algorithms for graphs of bounded treewidth via orthogonal range searching

Cited In (1)

• Title not available (Why is that?)

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)