Exact Shortest Path Queries for Planar Graphs Using Linear Space
Shay Mozes, Christian Sommer · arXiv (Cornell University) · 2010
We provide the first linear-space data structure with provable sublinear query time for exact point-topoint shortest path queries in planar graphs. We prove that for any planar graph G with non-negative arc lengths and for any > 0 there is a data structure that supports exact shortest path and distance queries in G with the following properties: the data structure can be created in time O(n lg(n) lg(1/ )), the space required is O(n lg(1/ )), and the query time is O(n ). Previous data structures by Fakcharoenphol and Rao (JCSS’06), Klein, Mozes, and Weimann (TransAlg’10), and Mozes and Wulff-Nilsen (ESA’10) with query time O(n lg n) use space at least Ω(n lgn/ lg lgn).