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

DOI10.1016/j.comgeo.2012.01.016zbMath1271.05031MaRDI 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

diameter; planar graph; Wiener index; distance oracle; shortest path distances

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

92E10: Molecular structure (graph-theoretic methods, methods of differential topology, etc.)