Constant Query Time (1 + ǫ)-Approximate Distance Oracle for Planar
Graphs1.
Qian-Ping Gu and Gengchun Xu

arXiv:1706.03108v1 [cs.DS] 9 Jun 2017

School of Computing Science, Simon Fraser University
Burnaby BC Canada V5A1S6
qgu@cs.sfu.ca,gxa2@sfu.ca
Abstract: We give a (1 + ǫ)-approximate distance oracle with O(1) query time for an undirected
planar graph G with n vertices and non-negative edge lengths. For ǫ > 0 and any two vertices u
˜ v) with stretch (1 + ǫ) in O(1) time. The oracle has size
and v in G, our oracle gives a distance d(u,
O(n log n((log n)/ǫ + f (ǫ))) and pre-processing time O(n log n((log3 n)/ǫ2 + f (ǫ))), where f (ǫ) =
2O(1/ǫ) . This is the first (1 + ǫ)-approximate distance oracle with O(1) query time independent of
ǫ and the size and pre-processing time nearly linear in n, and improves the query time O(1/ǫ) of
previous (1 + ǫ)-approximate distance oracle with size nearly linear in n.
key words: Distance oracle, planar graphs, approximate algorithms, graph decomposition

1

Introduction

Finding a distance between two vertices in a graph is a fundamental computational problem and
has a wide range of applications. For this problem, there is a rich literature of algorithms. This
problem can be solved by a single source shortest path algorithm such as the Dijkstra and BellmanFord algorithms. In many applications, it is required to compute the shortest path distance in an
extreme short time. One approach to meet such a requirement is to use distance oracles.
A distance oracle is a data structure which keeps the pre-computed distance information and
provides a distance between any given pair of vertices very efficiently. There are two phases in
the distance oracle approach. The first phase is to compute the data structure for a given graph
G and the second is to provide an answer for a query on the distance between a pair of vertices
in G. The efficiency of distance oracles is mainly measured by the time to answer a query (query
time), the memory space required for the data structure (oracle size) and the time to create the
data structure (pre-processing time). Typically, there is a trade-off between the query time and
the oracle size. A simple approach to compute a distance oracle for graph G of n vertices is to
solve the all pairs shortest paths problem in G and keep the shortest distances in an n × n distance
array. This gives an oracle with O(1) query time and O(n2 ) size. A large number of papers have
been published for distance oracles with better measures on the product of query time and oracle
size, see Sommer’s paper for a survey [16].
Planar graphs are an important model for many networks such as the road networks. Distance oracles for planar graphs have been extensively studied. Djidjev proves that for any oracle
1

A preliminary version of the paper appeared in the Proceedings of the 26th International Symposium on
Algorithms and Computation (ISAAC 2015) [8]

1

size S ∈ [n, n2 ], there is an exact distance oracle with query time O(n2/S) for weighted planar
graphs [6]. There are several exact distance oracles with size O(S) and more efficient query time
for different ranges of S, for example, an oracle by Wulff-Nilsen [19] with O(1) query time and
O(n2 (log log n)4 / log n) size for weighted
directed planar graphs and an oracle by Mozes and Som√
2.5
mer [15] with query time O((n/ S) log n) and size S ∈ [n log log n, n2 ] for weighted directed
planar graph. Readers may refer to Sommer’s survey paper [16] for more details.
Approximate distance oracles have been developed to achieve very fast query time and near
linear size for planar graphs. For vertices u and v in graph G, let dG (u, v) denote the distance between u and v. An oracle is called an α-approximate oracle or with stretch α for
˜ v) with dG (u, v) ≤ d(u,
˜ v) ≤ αdG (u, v) for u and v in
α ≥ 1 if it provides a distance d(u,
˜ v) with
G. An oracle is said to have an additive stretch β ≥ 0 if it provides a distance d(u,
˜
dG (u, v) ≤ d(u, v) ≤ dG (u, v) + β. For ǫ > 0, Thorup gives a (1 + ǫ)-approximate distance
oracle with O(1/ǫ) (resp. O(1/ǫ + log log ∆), where ∆ is the longest finite distance between
any pair of vertices in G) query time and O(n log n/ǫ) (resp. O(n(log ∆) log n/ǫ)) size for an
undirected (resp. directed) planar G with non-negative edge lengths [17]. A similar result
for undirected planar graphs is found independently by Klein [11]. Kawarabayashi et al. give
a (1 + ǫ)-approximate distance oracle with O((1/ǫ) log2 (1/ǫ) log log(1/ǫ) log∗ n) query time and
O(n log n log log(1/ǫ) log∗ n) size for undirected planar graphs with non-negative edge lengths
[10]. The query times of the oracles above are fast but still at least O(1/ǫ). Recently, WulffNilsen gives a (1 + ǫ)-approximate
distance oracle with O(n(log log n)2 /ǫ + log log n/ǫ2 )) size and
p
3 2
O((log log n) /ǫ +log log n log log((log log n)/ǫ2 )/ǫ2 ) query time for undirected planar graph with
non-negative edge lengths [20]. This result has a better trade-off between the query time and the
oracle size in the size of graph than those in [10, 11, 17].
Distance oracles with constant query time are of both theoretical and practical importance
[4, 5]. Our main result is an O(1) query time (1 + ǫ)-approximate distance oracle for undirected
planar graphs with non-negative edge lengths.
Theorem 1. Let G be an undirected planar graph with n vertices and non-negative edge lengths
and let ǫ > 0. There is a (1 + ǫ)-approximate distance oracle for G with O(1) query time,
O(n log n(log n/ǫ + f (ǫ))) size and O(n log n(log3 n/ǫ2 + f (ǫ))) pre-processing time, where f (ǫ) =
2O(1/ǫ) .
The oracle in Theorem 1 has a constant query time independent of ǫ and size nearly linear
in the graph size. This improves the query time of the previous works [10, 17] that are (nearly)
linear in 1/ǫ for non-constant ǫ. Wulff-Nilsen gives an O(1) time exact distance oracle for G with
size O(n2(log log n)4 / log n) [19]. There exists some constant c0 > 0 such that for 1ǫ < c0 log n, our
oracle has a smaller size.
The result in Theorem 1 can be generalized to an oracle described in the next theorem.
Theorem 2. Let G be an undirected planar graph with n vertices and non-negative edge lengths,
ǫ > 0 and 1 ≤ η ≤ 1/ǫ. There is a (1 + ǫ)-approximate distance oracle for G with O(η) query
time, O(n log n(log n/ǫ + f (ηǫ))) size and O(n log n(log3 n/ǫ2 + f (ηǫ))) pre-processing time, where
f (ηǫ) = 2O(1/(ηǫ)) .
2

Our results build on some techniques used in the previous approximate distance oracles for
planar graphs. Thorup [17] gives a (1 + ǫ)-approximate distance oracle for planar graph G with
O(1/ǫ) query time. Informally, some techniques used in the oracle are as follows: Decompose
G into a balanced recursive subdivision; G is decomposed into subgraphs of balanced sizes by
shortest paths and each subgraph is decomposed recursively until every subgraph is reduced to
a pre-defined size. A path Q intersects a path Q′ if V (Q) ∩ V (Q′ ) 6= ∅. A set Q of paths is
a path-separator for vertices u and v if every path between u and v intersects a path Q ∈ Q.
Vertices u and v are shortest-separated by a path Q if there exist a shortest path between u and v
that intersects Q. If vertices u and v have a path-separator Q then u and v is shortest-separated
by some path Q ∈ Q. For each subgraph X of G, let P(X) be the set of shortest paths used to
decompose X. For each path Q ∈ P(X) and each vertex u in X, a set PQ (u) of O(1/ǫ) vertices
called portals on Q is selected. For vertices u and v shortest-separated by some path Q in P(X),
minp∈PQ(u),q∈PQ (v),Q∈P(X) dG (u, p) + dG (p, q) + dG (q, v) is used to approximate dG (u, v). The oracle
keeps the distances dG (u, p) and dG (p, v).
The portal set PQ (u) above is vertex dependent. For a path Q in G of length d(Q), there is a set
PQ of O(1/ǫ) portals such that for any vertices u and v shortest-separated by Q, minp∈PQ dG (u, p)+
dG (p, v) ≤ dG (u, v) + ǫd(Q) [13]. Based on this and a scaling technique, Kawarabayashi et al. [10]
give another (1 + ǫ)-approximate distance oracle: Create subgraphs of G such that the vertices in
each subgraph satisfy certain distance property (scaling). Each subgraph H of G is decomposed
by shortest paths into a ρ-division of H which consists of O(|V (H)|/ρ) subgraphs of H, each has
size O(ρ). For each subgraph X of H, let B(X) be the set of shortest paths used to separate
X from the rest of H. For each path Q ∈ B(X), a portal set PQ is selected. For vertices u
and v shortest-separated by some path Q ∈ B(X), minp∈PQ ,Q∈B(X) dH (u, p) + dH (p, v) is used to
approximate dG (u, v). This oracle does not keep the distances dH (u, p) and dH (p, v) but uses the
distance oracle in [15] to get the distances. By choosing an appropriate value ρ, the oracle has a
better product of query time and oracle size than that of Thorup’s oracle.
We also use the scaling technique to create subgraphs of G. We decompose each subgraph H of
G into a balanced recursive subdivision as in Thorup’s oracle. For each subgraph X of H and each
shortest path Q used to decompose X, we choose one set PQ of O(1/ǫ) portals on Q for all vertices
in X. A new ingredient in our oracle is to use a more time efficient data structure to approximate
dG (u, v) instead of minp∈PQ ,Q∈P(X) dH (u, p) + dH (p, v). Using an approach in [18], we show that
the vertices in V (X) can be partitioned into s = f (ǫ) classes A1 , ..., As such that for every two
classes Ai and Aj , there is a key portal pij ∈ PQ and for any u ∈ Ai and v ∈ Aj , if u and v are
shortest-separated by Q then dH (u, pij ) + dH (pij , v) ≤ (1 + ǫ)dG (u, v) and dH (u, pij ) + dH (pij , v)
can be computed in O(1) time. This gives a (1 + ǫ)-approximate distance oracle with O(1) query
time.
Our computational model is word RAM, which models what we can program using standard
programming languages such as C/C++. In this model, a word is assumed big enough to store any
vertex identifier or distance. We also assume basic operations, which include addition, subtraction,
multiplication, bitwise operations (AND, OR, NEGATION) and left/right cyclic shift on a word
have unit time cost.
The rest of the paper is organized as follows. In the next section, we give preliminaries of the
3

paper and review the techniques on which our oracles build. In Section 3, we present distance
oracles with additive stretch. In Section 4, we give the (1 + ǫ)-approximate distance oracles which
use the additive stretch oracles as subroutines. The final section concludes the paper.

2

Preliminaries

An undirected graph G consists of a set V (G) of vertices and a set E(G) of edges. For a subset
A ⊆ E(G), we denote by V (A) the set of vertices incident to at least one edge of A. For A ⊆
E(G) and W ⊆ V (G), we denote by G[A] and G[W ] the subgraphs of G induced by A and W ,
respectively. A graph H is a subgraph of G if V (H) ⊆ V (G) and E(H) ⊆ E(G).

A path between vertices u and v in G is a sequence of edges e1 , .., ek , where ei = {vi−1 , vi }
for 1 ≤ i ≤ k, u = v0 , v = vk , and the vertices v0 , ..., vk are P
distinct. For any edge e, let l(e) be
the length of e. The length of path Q = e1 , ..., ek is d(Q) = 1≤i≤k l(ei ). A path Q is a shortest
path between vertices u and v if d(Q) is the minimum among those of all paths between u and v.
The distance between vertices u and v in G, denoted by dG (u, v), is the length of a shortest path
between u and v. For each vertex u in G, the eccentricity of u is λ(u) = maxv∈V (G) dG (u, v). The
radius of G is r(G) = minu∈V (G) λ(u). The diameter of G is d(G) = maxu∈V (G) λ(u).
A graph is planar if it has a planar embedding (a drawing on a sphere without edge crossing).
In the rest of this paper, graphs are undirected planar graphs with non-negative edge lengths
unless otherwise stated.

A basic approach in this paper is to decompose graph G into subgraphs by shortest paths. A set
P of shortest paths in graph G is a shortest path separator of G if G[V (G)\W ], W = ∪Q∈P V (Q),
has at least t ≥ 2 connected nonempty subgraphs G1 , .., Gt of G. A set Q of paths separates
subgraphs Gi and Gj , i 6= j, if for any vertex u in Gi and any vertex v in Gj , any path between u
and v intersects a path in Q. For a subgraph Gi of G, a set B(Gi ) of paths is a boundary of Gi if
B(Gi ) separates Gi and the rest of G and for every path Q ∈ B(Gi ), there is an edge connecting
Q and Gi . For α > 0, a shortest path separator P of G is called α-balanced if |V (Gi )| ≤ α|V (G)|
holds for every subgraph Gi . An α-balanced recursive subdivision of G is a structure that G is
decomposed into subgraphs G1 , .., Gt by an α-balanced separator and for each 1 ≤ i ≤ t, Gi
is decomposed recursively until each subgraph is reduced to a pre-defined size. In the recursive
decomposition of Gi , the subset of the shortest path separator P of G that forms a boundary
B(Gi ) of Gi is included in computing a shortest path separator of Gi . Let Tr be a shortest path
spanning tree of graph G rooted at a vertex r. Every path in Tr from the root r to any vertex
is a shorest path and called a root path. We use Thorup’s method [17] to compute a 21 -balanced
recursive subdivision using shortest path separators composed of root paths in Tr (based on the
result in [14], this can be done in linear time).
We now briefly describe Thorup’s method. Readers may refer to Section 2.5 in [17] for more
details. A recursive subdivision of G can be viewed as a rooted tree TG with each vertex of TG
(called a node, to be distinguished from a vertex of G) representing a subgraph of G and the root
node representing G. Each node in TG with node degree one is called a leaf node, otherwise an
internal node. We identify subgraphs with their corresponding nodes in TG when convenient. The
4

root node of TG has depth 0 and for any node X of TG , the depth of X is the number of edges
of TG from X to the root node. The depth of TG is the largest depth of any node in TG . For
each node X of TG , let B(X) be the set of root paths that forms a boundary of X (B(G) = ∅).
Let X ∪ B(X) denote the subgraph of G induced by V (X) ∪ V (B(X)). Let X + B(X) denote the
graph obtained by removing some vertices from X ∪ B(X) as follows: for every vertex v of B(X)
that has degree two in X ∪ B(X), its incident edges (u, v) and (v, w) are replaced by edge (u, w)
whose length is the sum of the length of (u, v) and that of (v, w). For each internal node X, a
1
-balanced shortest path separator P(X) of root paths is used to decompose X into subgraphs
2
X1 , .., Xt , t ≥ 2, as follows: Let W = V (P(X)) and X1∗ , .., Xt∗ be the connected components of
G[V (X + B(X)) \ W ]. Then E(Xi ) = E(X) ∩ E(Xi∗ ), 1 ≤ i ≤ t. Note that P(X) separates Xi
from Xj in X and B(X) ∪ P(X) separates Xi from Xj in G for 1 ≤ i, j ≤ t and i 6= j. We now
state some important properties of the 12 -balanced recursive subdivision in the next Lemma.
Lemma 1. [17] Given a graph G and a shortest path spanning tree Tr of G, a 12 -balanced recursive
subdivision TG of G can be computed in O(n log n) time such that for each internal node X of TG ,
|V (Xi )| ≤ |V (X)|/2 (1 ≤ i ≤ t) and |P(X)| = O(1), and for each node X, |B(X)| = O(1).
Moreover, for each node X of TG and each root path Q of Tr , if Q ∈ B(X), then Q ∈ P(X ′ ) for
some ancestor X ′ of X in TG .
The recursive subdivision of G in Lemma 1 will be used in our oracles. Note that since the size
of a subgraph is reduced by at least 1/2, the depth of TG is bounded above by log n. For every
vertex v ∈ V (G), we define the home of v, denoted by Xv , to be the node of TG of largest depth
that contains v. For any u, v ∈ V (G), we define Xu,v to be the nearest common ancestor of Xu
and Xv in TG . Harel and Tarjan show in [9] that after a linear time preprocessing, the nearest
common ancestor of any two nodes in a tree can be found in O(1) time.
Let Q be a shortest path in G and ǫ > 0. Thorup shows that for every vertex u in G, there is
subset PQ (u) ⊆ V (Q) of O(1/ǫ) vertices such that for any vertices u and v shortest-separated by
Q
dG (u, v) ≤
min
dG (v, p) + dG (p, q) + dG (q, v) ≤ (1 + ǫ)dG (u, v).
p∈PQ (u),q∈PQ (v)

The vertices of PQ (u) are called portals on Q for u. For every subgraph X in a 12 -balanced recursive
subdivision of G and every shortest path Q ∈ B(X) ∪ P(X), by keeping the distance from each
vertex u in X to every portal in PQ (u) explicitly, Thorup shows the following result.
Lemma 2. [17] For graph G and ǫ > 0, there is a (1 + ǫ)-approximate distance oracle with (1/ǫ)
query time, O(n log n/ǫ) size and O(n log3 n/ǫ2 ) pre-processing time. Especially for ǫ = 1, there
is a 2-approximate distance oracle for G with O(1) query time, O(n log n) size and O(n log3 n)
pre-processing time.
Our oracles will use this oracle for ǫ = 1 (any constant works) to get a rough estimation of
dG (u, v).
To reduce the query time to a constant independent of ǫ, we will use a portal set PQ independent
of vertex u. For vertices u and v shortest-separated by a path Q, dG (u, v) = minp∈V (Q) dG (u, p) +
dG (p, v). For a PQ ⊆ V (Q), minp∈PQ dG (u, p) + dG (p, v) approximates dG (u, v). The following
result will be used.
5

Lemma 3. [13] For a path Q in G, ǫ > 0 and D ≥ d(Q), a set PQ of O(1/ǫ) vertices in V (Q)
can be selected in O(|V (Q)|) time such that for any pair of vertices u and v shortest-separated by
Q, dG (u, v) ≤ minp∈PQ dG (u, p) + dG (p, v) ≤ dG (u, v) + ǫD.
The set PQ in Lemma 3 is called the ǫ-portal set (with respect to D) and every vertex in PQ
is called a portal. Given a path Q starting from a vertex r, ǫ > 0 and D ≥ d(Q), PQ can be
computed as follows: add r to PQ , traverse along Q from r and add a vertex v ∈ V (Q) to PQ if
dG (u, v) ≥ ǫD/2, where u is the last added portal in PQ . To apply the ǫ-portal set to our oracle,
we further need to guarantee dG (u, v) = Ω(D) for vertices u and v in question. We will use the
sparse neighborhood covers introduced in [1, 2, 3] of G to achieve this goal.
Lemma 4. [3] For G and γ ≥ 1, connected subgraphs G(γ, 1), . . . , G(γ, nγ ) of G with the following
properties can be computed in O(n log n) time:
1. For each vertex u in G, there is at least one G(γ, i) that contains u and every v with
dG (u, v) ≤ γ.
2. Each vertex u in G is contained in at most 18 subgraphs.
3. Each subgraph G(γ, i) has radius r(G(γ, i)) ≤ 24γ − 8.

3

Oracle with additive stretch

˜ v)
We first give a distance oracle which for any vertices u and v in G, and any ǫ0 > 0, returns d(u,
˜
with dG (u, v) ≤ d(u, v) ≤ dG (u, v) + 7ǫ0 d(G). Based on the scaling technique in [10] and Lemma 4,
this oracle will be extended to an oracle stated in Theorem 1 for G in the next section.
We start with a basic data structure which keeps the following information:
• A 21 -balanced recursive subdivision TG of G as in Lemma 1, each leaf node in TG has size
O(2(1/ǫ0 ) ).
• A table storing Xv for every v ∈ V (G).
• A data structure with O(1) query time to find the nearest common ancestor Xu,v of Xu and
Xv in TG for any u and v in G.
• For each internal node X of TG , an ǫ0 -portal set PQ for every shortest path Q ∈ P(X)∪B(X).
ˆ p) with
For every PQ , every u ∈ V (X) and every portal p ∈ PQ , distance d(u,
ˆ p) ≤ dG (u, p) + ǫ0 d(G).
dG (u, p) ≤ d(u,
• For every leaf node X and every pair of u and v in X, we keep
˜ v) = min{dX (u, v),
d(u,

min

p∈PQ,Q∈B(X)

6

ˆ p) + d(p,
ˆ v)}.
d(u,

The data structure above gives a distance oracle with 3ǫ0 d(G) additive stretch and O(1/ǫ0) query
˜ v) can be found in O(1) time.
time: Given vertices u and v, if Xu,v is a leaf node then d(u,
Otherwise, u and v must be shortest-separated by some path in B(Xu,v ) ∪ P(Xu,v ). Let
˜ v) =
d(u,

min

p∈PQ ,Q∈B(Xu,v )∪P(Xu,v )

ˆ p) + d(p,
ˆ v)
d(u,

and
q = argp∈PQ ,Q∈B(Xu,v )∪P(Xu,v ) min{dG (u, p) + dG (p, v)}.
ˆ q) ≤ dG (u, q) + ǫ0 d(G), d(q,
ˆ v) ≤ dG (q, v) + ǫ0 d(G) and Lemma 3,
From d(u,

˜ v) ≤ d(u,
ˆ q) + d(q,
ˆ v)
dG (u, v) ≤ d(u,
≤ dG (u, q) + dG (q, v) + 2ǫ0 d(G) ≤ dG (u, v) + 3ǫ0 d(G).

˜ v) can be computed in O(1/ǫ0 ) time because |PQ | = O(1/ǫ0 ) and |B(Xu,v ) ∪ P(Xu,v )| = O(1).
d(u,

We first reduce the query time for internal nodes in the above oracle to a constant independent
of ǫ0 and then analyse the preprocessing time of the distance oracle. For z > 0, let f (z) =
2O(1/z) . Based on an approach in [18], we show that for each internal node X and each path
Q ∈ B(X) ∪ P(X), the vertices in V (X) can be partitioned into f (ǫ0 ) classes such that for any
two classes Ai and Aj , there is a key portal pij ∈ PQ and for every u ∈ Ai and every v ∈ Aj
ˆ pij ) + d(p
ˆ ij , v) ≤ dG (u, v) + 7ǫ0 d(G). By keeping the classes and key
shortest-separated by Q, d(u,
portals, the query time is reduced to O(1). We first define the classes.

Definition 1. Let Q be a shortest path in G, r(G) ≤ D ≤ d(G) and PQ = {p1 ..., pl } be an
ǫ0 -portal set (with respect to D) on Q. The vertices of G are partitioned into classes based on
ˆ pi ), pi ∈ PQ as follows. For each vertex u, a vector ~Γu = (a1 , ..., al ) is defined such that for
d(u,
l
m
ˆ
1 ≤ i ≤ l, ai = d(u, pi )/(ǫ0 D) . Vertices u and v are in the same class if and only if ~Γu = ~Γv .
The following property of the classes defined above is straightforward.

Property 1. Let Q be a shortest path in G, r(G) ≤ D ≤ d(G) and PQ be an ǫ0 -portal set with
respect to D on Q. Let A be any class of vertices in G defined in Definition 1. For any two vertices
ˆ p) − ǫ0 D ≤ d(v,
ˆ p) ≤ d(u,
ˆ p) + ǫ0 D.
u, v ∈ A and any portal p ∈ PQ , d(u,
We show more properties of the classes defined above in the next two lemmas.
Lemma 5. Let Q be a shortest path in G, r(G) ≤ D ≤ d(G) and PQ be an ǫ0 -portal set with
respect to D on Q. Let Ai and Aj be any two classes of vertices in G defined in Definition 1.
There is a key portal pij ∈ PQ such that for any vertices u ∈ Ai and v ∈ Aj shortest-separated by
ˆ pij ) + d(p
ˆ ij , v) ≤ dG (u, v) + 7ǫ0 d(G).
Q, dG (u, v) ≤ d(u,
ˆ pi )+
Proof. We choose arbitrarily a vertex x ∈ Ai and a vertex y ∈ Aj . Let pij = argpi ∈PQ min{d(x,
ˆ i , y)} be the key portal. For any u ∈ Ai and v ∈ Aj shortest-separated by Q, let q =
d(p
ˆ pi ) + d(p
ˆ i , v)}. Then
argpi ∈PQ min{dG (u, pi ) + dG (pi , v)} and let p = argpi ∈PQ min{d(u,
ˆ p) + d(p,
ˆ v) ≤ d(u,
ˆ q) + d(q,
ˆ v)
d(u,
≤ dG (u, q) + dG (q, v) + 2ǫ0 d(G) ≤ dG (u, v) + 3ǫ0 d(G),
7

ˆ q) ≤ dG (u, q)+ǫ0 d(G), d(q,
ˆ v) ≤ dG (q, v)+ǫ0 d(G), PQ is an ǫ0 -portal set and Lemma 3.
because d(u,
From u, x ∈ Ai , Property 1 and D ≤ d(G),
ˆ pi ) ≤ d(x,
ˆ pi ) + ǫ0 D ≤ d(x,
ˆ pi ) + ǫ0 d(G) ≤ d(u,
ˆ pi ) + 2ǫ0 d(G)
d(u,

for every pi ∈ PQ . The same relations hold for v, y because they are in Aj . So
ˆ pij ) + d(p
ˆ ij , v) ≤ d(x,
ˆ pij ) + d(p
ˆ ij , y) + 2ǫ0 d(G)
d(u,
ˆ p) + d(p,
ˆ y) + 2ǫ0 d(G) ≤ d(u,
ˆ p) + d(p,
ˆ v) + 4ǫ0 d(G).
≤ d(x,
Therefore,
ˆ pij ) + d(p
ˆ ij , v) ≤ d(u,
ˆ p) + d(p,
ˆ v) + 4ǫ0 d(G)
dG (u, v) ≤ d(u,
≤ dG (u, v) + 7ǫ0 d(G).
This completes the proof of the lemma. 
Lemma 6. The total number of classes by Definition 1 is f (ǫ0 ).
Proof. Essentially, this result is proved by Weimann and Yuster in [18] but somehow hidden in
other details. Below we give a self-contained proof of the lemma. For each vector ~Γu = (a1 , .., al ),
let ~Γ∗u = (a1 , (a2 − a1 ), (a3 − a2 ), .., (al − al−1 )). Then ~Γu = ~Γv if and only if ~Γ∗u = ~Γ∗v . So we just
need to prove that the total number of different ~Γ∗u is f (ǫ0 ). From Definition 1,
&
' &
'
ˆ pi )
ˆ pi−1 )
d(u,
d(u,
|ai − ai−1 | =
−
ǫ0 D
ǫ0 D
≤

ˆ pi ) − d(u,
ˆ pi−1 )
d(u,
+1
ǫ0 D

≤

dG (u, pi ) − dG (u, pi−1)
dG (pi−1 , pi )
+2≤
+ 2.
ǫ0 D
ǫ0 D

Since PQ is an ǫ0 -portal set, l = O(1/ǫ0 ). So
X

2≤i≤l

|ai − ai−1 | ≤

dG (p1 , pl )
+ 2l = O(1/ǫ0 ).
ǫ0 D

Therefore there are 2O(1/ǫ0 ) different vectors of (a1 , |a2 − a1 | , |a3 − a2 | , .., |al − al−1 |). The i’th
element of (a1 , (a2 − a1 ), (a3 − a2 ), .., (al − al−1 )) is either |ai − ai−1 | or − |ai − ai−1 |. Therefore,
there are 2O(1/ǫ0 ) different ~Γ∗u . 
Notice that we can assume that for each internal node X, the number of classes Definition 1 is
at most |V (X)|2 because otherwise, instead of partitioning the vertices into classes, we can simply
use a |V (X)| × |V (X)| distance array to keep the shortest distance between every pair of vertices
in X.
Now we are ready to show a data structure DS0 for our oracle with 7ǫ0 d(G) additive stretch.
DS0 contains the basic data structure given above and the following additional information:
8

Q
• For each internal node X of TG and each shortest path Q ∈ B(X) ∪ P(X), let AQ
1 , ..., As be
the classes of vertices in V (X) defined in Definition 1. For each vertex u ∈ V (X), we give
Q
Q
an index IX
(u) with IX
(u) = i if u ∈ AQ
i ; and an s × s array CQ with CQ [i, j] containing the
Q
Q
Q
key portal pij for classes Ai and Aj .

ˆ p) for internal nodes as defined in the
We now describe how to compute the distances d(d,
basic data structure. The method is essentially the same as in the fast construction in [17], but
simpler as the portal sets we use are not vertex dependent. We use Lemma 1 to get the recursive
subdivision TG of G. Let Tr be the shortest path spanning tree of G as defined in Section 2 and
let D be the largest length of any root path of Tr . By a depth first search of Tr from r, we
compute an ǫ0 -portal set PQ (with respect to D) and an auxiliary (ǫ0 / log n)-portal set ΓQ (with
ˆ p) for
respect to D) for every Q ∈ P(X) ∪ B(X), X ∈ V (TG ). We compute the distances d(u,
every internal node X in a top-down traversal on TG from root G. We use Dijkstra’s algorithm
ˆ p) for every u in X and every p ∈ PQ ∪ ΓQ , Q ∈ P(X). Let X ⋆ B(X) denote
to compute d(u,
ˆ p′) for every u in
the graph obtained from adding to X ∪ B(X) the edges {u, p′ } with length d(u,
′
′
′
′
X and every p ∈ PQ′ ∪ ΓQ′ , where Q ∈ B(X) and Q ∈ P(X ) for some ancestor X ′ of X, and
then removing degree two vertices of B(X) as what we do for X + B(X). For the root node, the
computation is on G. For an internal node X 6= G, the computation is on X ⋆ B(X). Note that
X ⋆ B(X) may not be planar and since |B(X)| = O(1), |V (X ⋆ B(X))| is linear in the number of
edges of G incident to vertices of X plus the number of portals in each path. Notice that Q′ is in
ˆ p′ ) have
P(X ′ ) for some internal node X ′ which is an ancestor of X in TG . So the distances d(u,
ˆ p)
been computed when we construct X ⋆ B(X). Note that for some vertex u and portal p, d(u,
ˆ p) does not change: let Hi , 1 ≤ i, be the
may be computed multiple times. But the value of d(u,
ˆ
ˆ p) does not increase because the edge
graph on which d(u, p) is computed for the ith time; d(u,
ˆ p) does not decrease because Hi+1 is a subgraph of Hi
{u, p} is contained in Hi for i ≥ 2; and d(u,
for i ≥ 2. For X with |V (X)| ≥ log n/ǫ0 , we run Dijkstra’s algorithm using every p ∈ PQ ∪ ΓQ as
the source. For X with |V (X)| < log n/ǫ0 , we run Dijkstra’s algorithm using every u in X as the
ˆ p), p ∈ PQ ∪ ΓQ , for all internal nodes have been computed, we
source. After the distances d(u,
ˆ p) to the portals p ∈ PQ for every internal node.
only keep the distances d(u,
ˆ p) computed above meet the requirement
In the next lemma, we show that the distances d(u,
of DS0 .
Lemma 7. For every internal node X of TG , every vertex u in X and every portal p ∈ PQ ∪ ΓQ ,
ˆ p) ≤ dG (u, p) + ǫ0 d(G).
Q ∈ P(X), d(u,
Proof. For every internal node X of depth k in TG , every vertex u in X and every portal p ∈
ˆ p) ≤ dG (u, p) + kǫ0 d(G). For the root node
PQ ∪ ΓQ , Q ∈ P(X), we prove by induction that d(u,
log n
ˆ p) = dG (u, p) because the distances are computed on G. Assume that for every
(of depth 0), d(u,
ˆ p) ≤ dG (u, p) + (k−1)ǫ0 d(G). Let X be a node of
internal node of depth at most k − 1 ≥ 0, d(u,
log n

depth k. For u in X and p ∈ PQ ∪ ΓQ , Q ∈ P(X), let P (u, p) be a shortest path between u and p.
ˆ p) = dG (u, p) and the statement is proved. Otherwise,
If P (u, p) contains only edges in X then d(u,
P (u, p) can be partitioned into two subpaths P (u, y) and P (y, p), where every vertex of P (u, y)
except y is in X and y is a vertex of a path Q′ ∈ B(X). Note that y is incident to some vertex of
9

X so y appears in X ⋆ B(X). From the way ΓQ′ is computed and the fact that D ≤ d(G), where D
ǫ0
is used for computing ΓQ′ , there is a portal py ∈ ΓQ′ such that dQ′ (y, py ) = dG (y, py ) ≤ 2 log
d(G).
n
′
′
′
′
ˆ py ) is computed in X ⋆ B(X ′ )
Let X be an ancestor of X such that Q ∈ P(X ). Note that d(u,
and that y, py and X (and therefore P (u, y)) are all contained in X ′ ⋆ B(X ′ ). Therefore,
ˆ py ) ≤ d(P (u, y)) + dQ′ (y, py ) ≤ d(P (u, y)) +
d(u,

ǫ0
d(G)
2 log n

dG (py , p) ≤ d(P (y, p)) + dG (y, py ) ≤ d(P (y, p)) +

ǫ0
d(G).
2 log n

and

ˆ y , p) has been computed in a node X ′ which is an ancestor of X and has depth at
The distance d(p
ˆ y , p) ≤ dG (py , p) + (k−1)ǫ0 d(G). Because edges {u, py } and {py , p} with lengths
most k − 1. So d(p
log n
ˆ py ) and d(p
ˆ y , p) are contained in the graph X ⋆ B(X),
d(u,
ˆ p) ≤ d(u,
ˆ py ) + d(p
ˆ y , p)
d(u,
ǫ0
(k − 1)ǫ0
ǫ0
+ d(P (y, p)) +
+
d(G)
≤ d(P (u, y)) +
2 log n
2 log n
log n
kǫ0
d(G).
= dG (u, p) +
log n
ˆ p) ≤ ǫ0 d(G). 
Since each node in TG has depth at most log n, d(u,
The next three lemmas give the pre-procesing time, space requirement and query time for data
structure DS0 .
Lemma 8. For graph G and ǫ0 > 0, data structure DS0 can be computed in O(n(log3 n/ǫ20 +f (ǫ0 )))
time.
Proof. Let TG be the recursive subdivision of G and b = 2(1/ǫ0 ) . It takes O(n log n) time to
compute TG (Lemma 1). It takes O(n) time to compute the data structure that can answer the
least common ancestor of any two nodes in TG in O(1) time [9], O(n log n) time to compute Xv for
every v ∈ V (G), and O(n) time to compute PQ ∪ΓQ for every path Q ∈ B(X)∪P(X), X ∈ V (TG ).
P For every node X, let M(X) be the number of edges in G incident to vertices in X. Then
X∈TG M(X) = O(n log n). For every path Q, |PQ ∪ΓQ | = O(log n/ǫ0 ) and for every node X in TG ,
|B(X) ∪ P(X)| = O(1). From this, for each internal node X, X ⋆ B(X) has O(M(X) + log n/ǫ0 )
vertices and O(M(X) + log n/ǫ0 ) edges. Dijkstra’s algorithm is executed min{M(X), log n/ǫ0 }
ˆ p) for node X.
times for each node X. It takes O(M(X)(log n/ǫ0 )2 ) time to compute all d(u,
Since the sum of M(X) for all nodes X of the same depth is O(n), it takes O(n(log n/ǫ0 )2 ) time
for all internal nodes of the same depth. Since TG has depth O(log n), it takes O(n log3 n/ǫ20 ) time
ˆ p) for all internal nodes.
to compute all distances d(u,
˜ v) for a leaf node X, we first use Dijkstra’s algorithm to compute dX (u, v), taking
To find d(u,
every vertex of X as the source. This takes O(b2 log b) = O(b2 /ǫ0 ) time for one leaf node since
10

|V (X)| = O(b) and O(nb/ǫ0 ) time for all leaf nodes since the sum of |V (X)| for all leaf nodes X
is O(n). Then we compute
˜ v) = min{dX (u, v),
d(u,

min

p∈PQ,Q∈B(X)

ˆ p) + d(p,
ˆ v)}.
d(u,

From |PQ | = O(1/ǫ0 ) for Q ∈ B(X) and |B(X)| = O(1), this takes O(b2 /ǫ0 ) time for one leaf
˜ v) for all leaf nodes is
node and O(nb/ǫ0 ) time for all leaf nodes. The total time to compute d(u,
O(nb/ǫ0 )) = O(nf (ǫ0 )).
The value D for computing the classes can be found in O(n) time. Since there are O(n) internal
nodes, by Lemma 6, it takes O(nf (ǫ0 )(1/ǫ0 )) = O(nf (ǫ0 )) time to compute all classes and key
portals. Therefore, DS0 can be computed in O(n(log3 n/ǫ20 + f (ǫ0 ))) time. 
Lemma 9. For graph G and ǫ0 > 0, the space requirement for data structure DS0 is O(n(log n/ǫ0 +
f (ǫ0 ))).
Proof. Let TG be the recursive subdivision of G in DS0 and b = 2(1/ǫ0 ) . Each leaf node X has O(b)
˜ v) for u, v in the node. From this and
vertices and requires O(b2 ) space to keep the distances d(u,
the sum of |V (X)| for all leaf nodes is O(n), the space for all leaf nodes is O(nb) = O(nf (ǫ0 )). By
Lemma 1, the sum of |V (X)| for all nodes X in TG is O(n log n). From |B(X) ∪ P(X)| = O(1)
for every X and |PQ | = O(1/ǫ0 ) for each Q ∈ B(X) ∪ P(X), the total space for keeping the
ˆ v) between vertices and portals is O(n log n/ǫ0 ). By Lemma 6, the space for the
distances d(u,
Q
classes A1 , .., AQ
s in each internal node X is f (ǫ0 ) for every Q ∈ B(X) ∪ P(X). Since there are
O(n) internal nodes, the total space for the classes in all nodes is O(nf (ǫ0 )) = O(nf (ǫ0 )).
Therefore the space requirement for the oracle is O(n(log n/ǫ0 + f (ǫ0 ))). 
˜ v) with dG (u, v) ≤ d(u,
˜ v) ≤ dG (u, v) + 7ǫ0 d(G) can be
Lemma 10. For graph G and ǫ0 > 0, d(u,
computed in O(1) time for any u and v in G using data structure DS0 .
Proof. Let TG be the recursive subdivision of G in DS0 . Xu , Xv and Xu,v can be found in O(1)
˜ v) can be found in O(1) time. Otherwise, for each path
time. If Xu,v is a leaf node then d(u,
Q
Q
Q
Q ∈ B(Xu,v ) ∪ P(Xu,v ), assume that u ∈ AQ
i and v ∈ Aj , and let pij be the key portal for Ai and
AQ
j . By Lemma 5,
˜ v) =
d(u,

min

pQ
ij ,Q∈B(Xu,v )∪P(Xu,v )

ˆ pQ ) + d(p
ˆ Q , v) ≤ dG (u, v) + 7ǫ0 d(G).
d(u,
ij
ij

Since |B(X) ∪ P(X)| = O(1) and the key portal pQ
ij can be found in O(1) time for each path
˜
Q ∈ B(X) ∪ P(X), d(u, v) can be computed in O(1) time. 
From Lemmas 8, 9 and 10, we have the following result.
˜ v) with
Theorem 3. For graph G and ǫ0 > 0, there is an oracle which gives a distance d(u,
˜ v) ≤ dG (u, v) + 7ǫ0 d(G) for any vertices u and v in G with O(1) query time,
dG (u, v) ≤ d(u,
O(n(log n/ǫ0 + f (ǫ0 ))) size and O(n(log3 n/ǫ20 + f (ǫ0 ))) pre-processing time.
11

We can make the oracle in Theorem 3 a more generalized one: For integer η satisfying 1 ≤ η ≤
1/ǫ0 , we partition each path Q ∈ B(X) ∪ P(X) into η segments Q1 , .., Qη , compute the classes
Ql
Ql
l
AQ
1 , .., As of vertices in V (X) for each segment Ql , 1 ≤ l ≤ η, and key portal pij , and use
˜ v) =
d(u,

min

l
pQ
ij ,1≤l≤η,Q∈B(X)∪P(X)

ˆ pQl ) + d(p
ˆ Ql , v)
d(u,
ij
ij

to approximate dG (u, v). By this generalization, we get the following result.
Theorem 4. For graph G, ǫ0 > 0 and 1 ≤ η ≤ 1/ǫ0 , there is an oracle which gives a distance
˜ v) with dG (u, v) ≤ d(u,
˜ v) ≤ dG (u, v) + 7ǫ0 d(G) for any vertices u and v in G with O(η) query
d(u,
time, O(n(log n/ǫ0 + f (ηǫ0 ))) size and O(n(log3 n/ǫ20 + f (ηǫ0 ))) pre-processing time.

4

Oracle with (1 + ǫ) stretch

For ǫ > 0, by choosing an ǫ0 = 7cǫ where c > 0 is a constant, the oracle in Theorem 3 gives a
(1 + ǫ)-approximate distance oracle for graph G with dG (u, v) ≥ d(G)/c for every u and v in G.
For graph G with dG (u, v) much smaller than d(G) for some u and v, we use a scaling approach
as described in [10] to get a (1 + ǫ)-approximate distance oracle. The idea is to compute a set
of oracles as described in Theorem 3, each for a computed subgraph H of G. Given u and v, we
can find in O(1) time a constant number of subgraphs (and the corresponding oracles) such that
the minimum value returned by these oracles is a (1 + ǫ)-approximation of dG (u, v). Therefore a
(1 + ǫ)-approximate distance for any u, v can be computed in constant time. We assume ǫ > 5/n,
otherwise a naive exact distance oracle with O(1) query time and O(n2 ) space can be used to
prove Theorem 1.
Let lm be the smallest edge length in G. We assume lm ≥ 1 and the case where lm < 1 can
be easily solved in a similar way by normalizing the length of each edge e of G to l(e)/lm . For
each scale γ ∈ {2i |0 ≤ i ≤ ⌈log d(G)⌉}, we contract every edge e = {u, v} of length l(e) < γ/n2
in G and then compute a sparse cover Cγ = {G(γ, j), j = 1, ..., nγ } of G as in Lemma 4. Each
edge of G appears in subgraphs G(γ, j) for O(log n) different scales [10]. This is because every
edge e only appears in scales γ satisfying l(e)/24 ≤ γ ≤ l(e)n2 . The data structure DS1 for our
(1 + ǫ)-approximate distance oracle keeps the following information:
• A 2-approximate distance oracle DST of G in Lemma 2.
• Subgraphs G(γ, j) and for each subgraph G(γ, j), an oracle DS0 (γ, j) in Theorem 3 with
ǫ0 = ǫ/c′ , c′ > 0 is a constant to be specified below.
• For every v ∈ V (G) and every scale γ, the index j of every subgraph G(γ, j) that contains
v.
˜ v) with dG (u, v) ≤ d(u,
˜ v) ≤ (1 + ǫ)dG (u, v) can be
Lemma 11. For graph G and ǫ > 0, d(u,
computed in O(1) time for any u and v in G using data structure DS1 .
12

Proof. Given vertices u and v in G, oracle DST gives d˜T (u, v) with dG (u, v) ≤ d˜T (u, v) ≤ 2dG (u, v)
˜
in O(1) time (Lemma 2). If d˜T (u, v) = 0 then 0 is returned as dG (u, v). Otherwise, given
l dT (u, v),
m
a scale γ with γ/2 < d˜T (u, v) ≤ γ can be found by computing the most significant bit of d˜T (u, v) .

In the word RAM model with unit costs for basic operations, this can be computed in O(1) time
using the fusion tree data structure proposed in [7]. By Lemma 4, there is a G(γ, j) that contains u
and every w with dG (u, w) ≤ dG (u, v) ≤ γ and d(G(γ, j)) = O(γ) = O(dG (u, v)). Therefore there
exists a constant c1 > 0 (96 would do) such that d(G(γ, j)) ≤ c1 dG (u, v). It is easy to see that
DS0 (γ, j) returns a minimum distance among all the oracles at this scale containing u, v. By oracle
DS0 (γ, j), we get a distance d˜0 (u, v) with dG(γ,j) (u, v) ≤ d˜0 (u, v) ≤ dG(γ,j) (u, v) + 7ǫ0 d(G(γ, j)).
Since G(γ, j) is a subgraph obtained from G with every edge e with l(e) < γ/n2 contracted,
dG(γ,j) (u, v) ≤ dG (u, v). Let L be the largest sum of the lengths of the contracted edges in any path
in G. Then dG (u, v) ≤ dG(γ,j)(u, v) + L and L < γ/n ≤ 54 ǫdG (u, v), from γ < 2d˜T (u, v) ≤ 4dG (u, v)
˜ v) = d˜0 (u, v) + γ/n. Then
and ǫ > 5/n. Let d(u,

˜ v) ≤ dG(γ,j) (u, v) + 7ǫ0 d(G(γ, j)) + γ/n
dG (u, v) ≤ d(u,
4
ǫ
≤ dG (u, v) + 7c1 ′ dG (u, v) + ǫdG (u, v).
c
5
By choosing c′ = 35c1 , we have dG (u, v) ≤ d˜G (u, v) ≤ (1 + ǫ)dG (u, v). By Lemma 2, it takes O(1)
time to compute d˜T (u, v). From Lemma 4, there are O(1) graphs G(γ, j) containing u and v.
˜ v). 
From this and Theorem 3, it takes O(1) time to compute d(u,
Lemma 12. Data structure DS1 requires O(n log n(log n/ǫ + f (ǫ))) space and can be computed in
O(n log n(log3 n/ǫ2 + f (ǫ))) time.
Proof. DST requires O(n log n) space. Each DS0 (γ, j) requires O(nγj log nγj /ǫ + nγj f (ǫ)) space,
where nγj = |V (G(γ, j))|. Each edge e of G appearsP
in O(log n) different scales γ and in each scale
e appears in O(1) subgraphs G(γ, j). From this, γ,j nγj = O(n log n) and DS1 requires space
O(n log n(log n/ǫ + f (ǫ))).

DST can be computed in O(n log3 n) time and the sparse neighborhood covers can be computed
in O(n log2 n) time. The time for computing DS0 (γ, j) for each G(γ, j) is O(nγj log3 nγj /ǫ2 + f (ǫ)).
Therefore, DS1 can be computed in O(n log n(log3 n/ǫ2 + f (ǫ)) time. 
From Lemmas 11 and 12, we get Theorem 1 which is restated below.

Theorem 1. For ǫ > 0, there is a (1 + ǫ)-approximate distance oracle for G with O(1) query time,
O(n log n(log n/ǫ + f (ǫ))) size and O(n log n(log3 n/ǫ2 + f (ǫ))) pre-processing time.
Using the oracle in Theorem 4 instead of DS0 , we get Theorem 2.

5

Concluding remarks

It is open whether there is a (1 + ǫ)-approximate distance oracle with O(1) query time and
size nearly linear in n for weighted directed planar graphs. For undirected planar graphs, it
13

is interesting to reduce oracle size and pre-processing time (the function f (ǫ)) for the oracles in
this paper. Experimental studies for fast query time distance oracles are worth investigating.

References
[1] Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing 28(1), 263-277 (1998).
[2] Awerbuch, B., Peleg, D.: Sparse partitions. In: Proceedings of the 31st IEEE Annual Symposium on Foundations of Computer Science (FOCS1990), 503-513 (1990).
[3] Busch, C., LaFortune, R., Tirthapura, S.: Improved sparse covers for graphs excluding a
fixed minor. In: Proceedings of the 26th Annual ACM symposium on Principles of Distributed
Computing (PODC2007), 61-70 (2007).
[4] Chechik, S.: Approximate distance oracle with constant query time. In: Proceedings of the
46th Annual ACM symposium on Theory of computing (STOC2014), 654-663 (2014).
[5] Delling, N., Goldberg, A., Pajor, T., Werneck, R.: Robust exact distance queries on massive
networks. In: Microsoft Research Technique Report, MSR-TR-2014-12 (2014).
[6] Djidjev, H.: Efficient algorithms for shortest path problems on planar graphs. In: Proceedings of the 22nd International Workshop on Graph-Theoretical Concepts in Computer Science
(WG1996), 151-165 (1996).
[7] Fredman, M. L., Willard, D. E.. Surpassing the information theoretic bound with fusion trees.
Journal of computer and system sciences, 47(3), 424-436 (1993).
[8] Gu, Q., Xu, G.: Constant query time (1 + ǫ)-approximate distance oracle for planar graphs.
In: Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC
2015), LNCS 9472, 625-636 (2015).
[9] Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestor. SIAM Journal on
Computing 13, 338-355 (1984).
[10] Kawarabayashi, K., Sommer, C., Thorup, M.: More compact oracles for approximate distances in undirected planar graphs. In: Proceedings of the 24th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA2013), 550-563 (2013).
[11] Klein, P.N.: Preprocessing an undirected planar network to enable fast approximate distance
queries. In: Proceedings of the 13th annual ACM-SIAM symposium on Discrete Algorithms
(SODA2002), 820-827 (2002).
[12] Klein, P.N., Mozes, S. Sommer, C.: Structured recursive separator decompositions for planar
graphs in linear time. In: Proceedings of the 45th Annual ACM symposium on Theory of
computing (STOC2013), 505-514 (2013).
14

[13] Klein, P.N., Subramanian, S.: A fully dynamic approximation scheme for shortest paths in
planar graphs. Algorithmica 22(3), 235-249 (1998).
[14] Lipton, R.J., Tarjan, R.E., A separator theorem for planar graphs. SIAM Journal on Applied
Mathematics 36(2), 177-189 (1979).
[15] Mozes, S., Sommer, C.: Exact distance oracles for planar graphs. In: Proceedings of the 23rd
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2012), 209-222 (2012).
[16] Sommer, C.: Shortest-path queries in static networks. ACM Computing Surveys, 46(4), Article No. 45, (2014).
[17] Thorup, M. Compact oracles for reachability and approximate distances in planar digraphs.
Journal of the ACM (JACM) 51(6), 993-1024 (2004).
[18] Weimann, O., Yuster, R.: Approximating the diameter of planar graphs in near linear time. In:
Proceedings of the 40th International Colloquium on Automata, Languages, and Programming
(ICALP2013), LNCS7965, 828-839 (2013).
[19] Wulff-Nilsen, C.: Algorithms for planar graphs and graphs in metric spaces. Ph.D. Thesis,
University of Copenhagen, (2010).
[20] Wulff-Nilsen, C.: Approximate Distance Oracles for Planar Graphs with Improved Query
Time-Space Tradeoff. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA2016), 351-362 (2016).

15

