Reproduce “Almost Optimal Distance Oracles for Planar Graphs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann
Researchers present new exact distance oracles for directed, weighted planar graphs, achieving near-linear space with polylogarithmic query times and sub-polynomial tradeoffs. This work establishes the closest known approximations to the theoretical ideal of linear space and constant query time.
Key insights
- Recursive r-division and external Voronoi diagrams allow for efficient hierarchical decomposition, extending beyond local computations within graph pieces to broader graph complements.
- The use of 'coarse trees' enables the determination of path relationships between boundary vertices without needing to store large, explicit MSSP data structures.
- Achieving polylogarithmic query times with nearly linear space demonstrates that exact distance queries can be highly efficient in planar graphs without prohibitive memory costs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.