Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.26313 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917364430274560 |
|---|---|
| author | Mozes, Shay Prigan, Daniel |
| author_facet | Mozes, Shay Prigan, Daniel |
| contents | We prove that, up to subpolynomial or polylogarithmic factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs. Namely, we show how given an $n$-vertex weighted directed planar graph $G$, one can compute in $n^{1+o(1)}$ time and space a representation of $G$ from which one can extract the exact distance between any two vertices of $G$ in $\log^{2+o(1)}(n)$ time. Previously, it was only known how to construct oracles with these space and query time in $n^{3/2+o(1)}$ time [STOC 2019, SODA 2021, JACM 2023]. We show how to construct these oracles in $n^{1+o(1)}$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26313 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distances in Planar Graphs are Almost for Free! Mozes, Shay Prigan, Daniel Data Structures and Algorithms We prove that, up to subpolynomial or polylogarithmic factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs. Namely, we show how given an $n$-vertex weighted directed planar graph $G$, one can compute in $n^{1+o(1)}$ time and space a representation of $G$ from which one can extract the exact distance between any two vertices of $G$ in $\log^{2+o(1)}(n)$ time. Previously, it was only known how to construct oracles with these space and query time in $n^{3/2+o(1)}$ time [STOC 2019, SODA 2021, JACM 2023]. We show how to construct these oracles in $n^{1+o(1)}$ time. |
| title | Distances in Planar Graphs are Almost for Free! |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.26313 |