Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Exact Distance Oracles for Planar Graphs   We present new and improved data structures that answer exact node-to-node
distance queries in planar graphs. Such data structures are also known as
distance oracles. For any directed planar graph on n nodes with non-negative
lengths we obtain the following:
  * Given a desired space allocation $S\in[n\lg\lg n,n^2]$, we show how to
construct in $\tilde O(S)$ time a data structure of size $O(S)$ that answers
distance queries in $\tilde O(n/\sqrt S)$ time per query.
  As a consequence, we obtain an improvement over the fastest algorithm for
k-many distances in planar graphs whenever $k\in[\sqrt n,n)$.
  * We provide a linear-space exact distance oracle for planar graphs with
query time $O(n^{1/2+eps})$ for any constant eps>0. This is the first such data
structure with provable sublinear query time.
  * For edge lengths at least one, we provide an exact distance oracle of space
$\tilde O(n)$ such that for any pair of nodes at distance D the query time is
$\tilde O(min {D,\sqrt n})$. Comparable query performance had been observed
experimentally but has never been explained theoretically.
  Our data structures are based on the following new tool: given a
non-self-crossing cycle C with $c = O(\sqrt n)$ nodes, we can preprocess G in
$\tilde O(n)$ time to produce a data structure of size $O(n \lg\lg c)$ that can
answer the following queries in $\tilde O(c)$ time: for a query node u, output
the distance from u to all the nodes of C. This data structure builds on and
extends a related data structure of Klein (SODA'05), which reports distances to
the boundary of a face, rather than a cycle.
  The best distance oracles for planar graphs until the current work are due to
Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For
$\sigma\in(1,4/3)$ and space $S=n^\sigma$, we essentially improve the query
time from $n^2/S$ to $\sqrt{n^2/S}$.

3
The categories of this paper are: physics
21
The categories of this paper are: adap-org
12
The categories of this paper are: nucl-th
18
The categories of this paper are: econ
34
The categories of this paper are: chem-ph
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
13
The categories of this paper are: quant-ph
30
The categories of this paper are: q-alg
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc
26
The categories of this paper are: bayes-an
25
The categories of this paper are: patt-sol
16
The categories of this paper are: stat
4
The categories of this paper are: cond-mat
6
The categories of this paper are: astro-ph