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

DOI10.1016/j.comgeo.2012.01.016zbMath1271.05031OpenAlexW1992608637MaRDI QIDQ359743

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)

Cites Work

• Unnamed Item
• 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
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs

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