# More Compact Oracles for Approximate Distances in Undirected Planar Graphs

@inproceedings{Kawarabayashi2013MoreCO, title={More Compact Oracles for Approximate Distances in Undirected Planar Graphs}, author={Ken-ichi Kawarabayashi and Christian Sommer and Mikkel Thorup}, booktitle={SODA}, year={2013} }

Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and the main focus of this paper. Unless stated otherwise, we assume all graphs to be planar and undirected.
In FOCS 2001 (J. ACM 2004), Thorup introduced approximate distance oracles for planar graphs (concurrent with Klein, SODA 2002). Thorup proved… Expand

#### Tables and Topics from this paper

#### 25 Citations

Fast and Compact Exact Distance Oracle for Planar Graphs

- Mathematics, Computer Science
- 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
- 2017

An O(n 5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs is introduced. Expand

Exact distance oracles for planar graphs

- Computer Science, Mathematics
- SODA
- 2012

New and improved data structures that answer exact node-to-node distance queries in planar graphs and an exact distance oracle of space O(n) such that for any pair of nodes at distance l the query time is O(min{l, √ n}). Expand

Better Tradeoffs for Exact Distance Oracles in Planar Graphs

- Computer Science, Mathematics
- SODA
- 2018

This oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5/3)-space and answers queries in O(log n) time. Expand

Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff

- Computer Science, Mathematics
- SODA
- 2016

We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed e > 0. we present a (1 + e)-approximate distance oracle with O(n(log log n)2) space and… Expand

Efficient Vertex-Label Distance Oracles for Planar Graphs

- Mathematics, Computer Science
- Theory of Computing Systems
- 2017

It is shown how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Expand

Almost optimal distance oracles for planar graphs

- Computer Science, Physics
- STOC
- 2019

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within… Expand

Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs

- Computer Science, Mathematics
- SoCG
- 2018

The first near-linear-time (1 + epsilon)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O(n log^2 n) time, is presented, improving the near-O(n^{3/2})-time algorithm of Gao and Zhang [STOC 2003]. Expand

Efficient Vertex-Label Distance Oracles for Planar Graphs

- Mathematics, Computer Science
- WAOA
- 2015

The best prior result for the undirected case has similar space and preprocessing bounds, but exponentially slower query time, and the same data structure for directed planar graphs with slightly worse performance is given. Expand

The Space-Stretch-Time Tradeoff in Distance Oracles

- Mathematics, Computer Science
- ESA
- 2014

New distance oracles for computing distances of stretch less than 2 on general weighted undirected graphs and for any integer k are presented, which significantly improves the state-of-the-art for each point in the space-stretch-time tradeoff space. Expand

Almost Optimal Distance Oracles for Planar Graphs ∗ Panagiotis Charalampopoulos

- 2019

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within… Expand

#### References

SHOWING 1-10 OF 95 REFERENCES

Exact distance oracles for planar graphs

- Computer Science, Mathematics
- SODA
- 2012

New and improved data structures that answer exact node-to-node distance queries in planar graphs and an exact distance oracle of space O(n) such that for any pair of nodes at distance l the query time is O(min{l, √ n}). Expand

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs

- Computer Science, Mathematics
- ICALP
- 2011

For planar graphs, bounded-genus graphs, and minor-excluded graphs, this paper gives distance-oracle constructions that require only O(n) space, and the big O hides only a fixed constant, independent of e and independent of genus or size of an excluded minor. Expand

Distance Oracles for Sparse Graphs

- Mathematics, Computer Science
- 2009 50th Annual IEEE Symposium on Foundations of Computer Science
- 2009

A new lower bound for approximate distance oracles in the cell-probe model is given, which holds even for sparse (polylog(n)-degree) graphs, and it is not an "incompressibility" bound: it is a three-way tradeoff between space, stretch, and query time. Expand

Approximate distance oracles

- Mathematics, Computer Science
- J. ACM
- 2005

The most impressive feature of the data structure is its constant query time, hence the name "oracle", and it provides faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs. Expand

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

- Computer Science, Mathematics
- Comput. Geom.
- 2013

It is shown that the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G can be computed in o ( n 2 ) time with O ( n ) space. Expand

Approximate distance oracles with improved preprocessing time

- Computer Science, Mathematics
- SODA
- 2012

This work shows that for some universal constant c, a (2k − 1)-approximate distance oracle for G of size O(kn1+1/k) can be constructed in [EQUATION] time and can answer queries in O(k) time and gives an oracle which is faster for smaller k. Expand

Oracles for bounded-length shortest paths in planar graphs

- Mathematics, Computer Science
- TALG
- 2006

A new approach for answering short path queries in planar graphs, motivated by a practical situation where nodes or links of a network may be temporarily out of service, which can be easily generalized to other wide classes of graphs. Expand

On-Line Algorithms for Shortest Path Problems on Planar Digraphs

- Computer Science
- WG
- 1996

Efficient algorithms for answering shortest path queries in digraphs with small separators and, in particular, in planarDigraphs are described, for any class ofdigraphs for which an O(√n) separator theorem holds. Expand

Improved Distance Queries in Planar Graphs

- Computer Science, Mathematics
- WADS
- 2011

This paper presents three data structures that answer distance queries between two arbitrary vertices in a planar graph, each with its own advantage over previous data structures, which improves the query time of data structures of linear space. Expand

Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths

- Mathematics, Computer Science
- 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
- 2006

An O(n2 log n) algorithm is presented to construct a data structure of size O(kn1+1k/) for all integers k ges 2 and a new generic scheme for all-pairs approximate shortest paths is used for these results. Expand