TY - CONF

T1 - Optimal Approximate Distance Oracle for Planar Graphs

AU - Le, Hung

AU - Wulff-Nilsen, Christian

PY - 2022

Y1 - 2022

N2 - A (1+ϵ)-approximate distance oracle of an edge-weighted graph is a data structure that returns an approximate shortest path distance between any two query vertices up to a (1+ϵ) factor. Thorup (FOCS 2001, JACM 2004) and Klein (SODA 2002) independently constructed a (1+ϵ)-approximate distance oracle with O(nlogn) space, measured in number of words, and O(1) query time when G is an undirected planar graph with n vertices and ϵ is a fixed constant. Many follow-up works gave (1+ϵ)-approximate distance oracles with various trade-offs between space and query time. However, improving O(nlogn) space bound without sacrificing query time remains an open problem for almost two decades. In this work, we resolve this problem affirmatively by constructing a (1+ϵ)-approximate distance oracle with optimal O(n) space and O(1) query time for undirected planar graphs and fixed ϵ.We also make substantial progress for planar digraphs with non-negative edge weights. For fixed ϵ>0, we give a (1+ϵ)-approximate distance oracle with space o(nlog(Nn)) and O(loglog(Nn) query time; here N is the ratio between the largest and smallest positive edge weight. This improves Thorup's (FOCS 2001, JACM 2004) O(nlog(Nn)logn) space bound by more than a logarithmic factor while matching the query time of his structure. This is the first improvement for planar digraphs in two decades, both in the weighted and unweighted setting.

AB - A (1+ϵ)-approximate distance oracle of an edge-weighted graph is a data structure that returns an approximate shortest path distance between any two query vertices up to a (1+ϵ) factor. Thorup (FOCS 2001, JACM 2004) and Klein (SODA 2002) independently constructed a (1+ϵ)-approximate distance oracle with O(nlogn) space, measured in number of words, and O(1) query time when G is an undirected planar graph with n vertices and ϵ is a fixed constant. Many follow-up works gave (1+ϵ)-approximate distance oracles with various trade-offs between space and query time. However, improving O(nlogn) space bound without sacrificing query time remains an open problem for almost two decades. In this work, we resolve this problem affirmatively by constructing a (1+ϵ)-approximate distance oracle with optimal O(n) space and O(1) query time for undirected planar graphs and fixed ϵ.We also make substantial progress for planar digraphs with non-negative edge weights. For fixed ϵ>0, we give a (1+ϵ)-approximate distance oracle with space o(nlog(Nn)) and O(loglog(Nn) query time; here N is the ratio between the largest and smallest positive edge weight. This improves Thorup's (FOCS 2001, JACM 2004) O(nlog(Nn)logn) space bound by more than a logarithmic factor while matching the query time of his structure. This is the first improvement for planar digraphs in two decades, both in the weighted and unweighted setting.

U2 - 10.1109/FOCS52979.2021.00044

DO - 10.1109/FOCS52979.2021.00044

M3 - Paper

SP - 1

EP - 61

T2 - 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021))

Y2 - 7 February 2022 through 11 February 2022

ER -