Near-Optimal Compression for the Planar Graph Metric∗
Amir Abboud

†

Paweł Gawrychowski

‡

Shay Mozes§

Oren Weimann¶

Abstract

arXiv:1703.04814v1 [cs.DS] 14 Mar 2017

The Planar Graph Metric Compression Problem is to compactly encode the distances
among k nodes in a planar graph of size n. Two naïve solutions are to store the graph
using Opnq bits, or to explicitly store the distance matrix with Opk 2 log nq bits. The only
lower bounds are from the seminal work of Gavoille, Peleg, Prennes, and Raz [SODA’01],
who rule out compressions into a polynomially smaller number of bits, for weighted planar
?
graphs, but leave a large gap for unweighted planar graphs. For example, when k “ n,
the upper bound is Opnq and their constructions imply an Ωpn3{4 q lower bound. This gap
is directly related to other major open questions in labelling schemes, dynamic algorithms,
and compact routing.
?
Our main result is a new compression of the planar graph metric into Õpminpk 2 , k ¨ nqq
bits, which is optimal up to log factors. Our data structure breaks an Ωpk 2 q lower bound
of Krauthgamer, Nguyen, and Zondiner [SICOMP’14] for compression using minors, and
the lower bound of Gavoille et al. for compression of weighted planar graphs. This is an
unexpected and decisive proof that weights can make planar graphs inherently more
? complex.
Moreover, we design a new Subset Distance Oracle for planar graphs with Õp k ¨ nq space,
and Õpn3{4 q query time.
Our work carries strong messages to related fields. In particular, the famous Opn1{2 q
vs. Ωpn1{3 q gap for distance labelling schemes in planar graphs cannot be resolved with the
current lower bound techniques.

∗

Supported in part by Israel Science Foundation grant 794/13.
Stanford University, Department of Computer Science, abboud@cs.stanford.edu.
‡
University of Haifa, Department of Computer Science, gawry@mimuw.edu.pl.
§
Interdisciplinary Center Herzliya, Efi Arazi School of Computer Science, smozes@idc.ac.il.
¶
University of Haifa, Department of Computer Science, oren@cs.haifa.ac.il.
†

1

1

Introduction

The shortest path metric of planar graphs is one of the most popular and well-studied metrics
in Computer Science. Countless papers, surveys, and textbooks address the computational
challenges that arise when dealing with it. In this paper, we address a core problem about this
metric that has remained poorly understood. We ask: How compressible is it? That is, how
many bits do we need, information theoretically, in order to describe a set of distances in a
planar graph?
As we discuss shortly, a better understanding of this core question is crucial to making
progress on some of the biggest open problems in other well-studied subjects such as Sparsification, Labeling Schemes, Dynamic Algorithms, and Compact Routing Schemes.
First, let us define our problem more formally. In the Metric Compression problem, we are
given a set S of k points in some metric space with distance function d, such as the metric of
distances in an n node planar graph, and the goal is to find an encoding C that is as short as
possible, yet still allows us to compute dpvi , vj q for any two points vi , vj P S.
Definition 1.1 (The Planar Graph Metric Compression Problem). Given an unweighted, undirected planar graph G on n nodes, and a subset S of k distinguished nodes in G, compute a bit
string C that encodes the distances between all pairs of nodes in S. That is, there is a decoding
function f that given the encoding C and any two nodes vi , vj P S returns the vi -to-vj distance
in G (i.e., f pvi , vj , Cq “ dG pvi , vj q).
There are two naïve ways to solve this problem. First, we can store all the distances explicitly
as a k ˆ k matrix in the encoding C. The distance in a graph on n nodes is some number in
t0, 1, . . . , nu, and so this matrix can be encoded using Opk 2 log nq bits. The second option, which
is better whenever k 2 ą n, is to let the encoding be the graph G itself. Naïvely, this is Opn log nq
bits, and more sophisticated encodings give Opnq [23,34,78,93]. Using the Õp¨q notation to hide
polylog factors, we get a naïve upper bound of Õpmintk 2 , nuq for our problem. Is this the best
possible, or could there be a much better compression into Õpk ¨ nε q or even Õpkq bits?
For context, let us look at other metrics. One example of a metric that admits an ultraefficient compression into Õpkq bits is the metric of trees or bounded treewidth graphs [32, 48].
For most metrics of interest, however, the exact or lossless version of the compression problem is
too difficult and no non-trivial upper bounds, beyond log-factor improvements, are possible. For
example, in general (non-planar) graphs there is a simple Ωpk 2 q lower bound: in any compression,
k
each of the 2p2q possible graphs on k nodes must be encoded differently. Instead, it is popular
to seek the optimal lossy compression from which the metric can be recovered approximately,
e.g. up to a multiplicative p1 ` εq error. For example, the classical Johnson-Lindenstrauss
[10, 60] embedding allows one to compress a set of k points in Euclidean d-dimensional space
into roughly Opk{ε2 ¨ log2 kq bits, so that the distances between the points can be recovered up
to a p1 ` εq factor, and a recent breakthrough of Indyk and Wagner [58] reduced the bound to
roughly Opk{ε2 ¨ log k ¨ log p1{εqq which is tight up to a log p1{εq factor.
Indeed, if we are willing to pay a p1 ` εq error, there are ingenious compressions of the planar
graph metric into Õpkq bits [66, 70, 88]. But do we have to pay this error, or are planar graphs
restricted enough to allow for non-trivial compression?
Open Question 1. Can we beat Õpmintk 2 , nuq bits for planar graph metric compression?
There are some lower bounds in our way. From the seminal work of Gavoille, Peleg, Pérennes,
and Raz [48] we know that the metric of weighted planar graphs, where the edge weights are
polynomially bounded, does not admit any non-trivial compression. The authors show that any
Boolean k ˆk matrix can be “encoded” using the distances among a set of 2k nodes in a weighted
2

planar graph on n “ Opk 2 q nodes, where the edge weights are in rks. Since we cannot compress
an arbitrary k ˆ k matrix into opk 2 q bits, we get a nearly-tight lower bound of Ωpmintk 2 , nuq
for weighted planar graphs. For unweighted planar graphs, Gavoille et al. simply subdivide the
edges in their construction and the number?of nodes in the encoding grows to n “ Θpk 3 q, which
leads to a much weaker lower bound of Ωp k ¨ nq (see Section 4 for more details). For example,
?
when k “ n, the upper bound is Õpnq and the lower bound is Ωpn3{4 q. This subdivision of
edges is rather naïve, and the overall lower bound construction does not seem to capture the
full power of the planar graph metric. In fact, it can be simulated by a grid graph [4]. This
naturally suggests the following intriguing challenge of finding a more clever encoding of matrices
into planar graphs, which would lead to a negative resolution to Open Question 1.
Challenge 1. Can we encode an arbitrary k ˆ k Boolean matrix M using the distances among
a subset of 2k nodes tv1 , . . . , v2k u in an unweighted planar graph with Opk 2 q vertices, so that we
can determine M ri, js by only looking at the distance between vi and vk`j in our graph?
Before presenting our results, let us discuss the state of the art on questions that are closely
related to ours, in which we are interested in data structures that are not only as succinct as
possible, but also have other desirable features. Along the way, we give further reasons to be
pessimistic about the possibility of a non-trivial compression.
Sparsification. A natural way to compress a graph is by deleting or contracting some of its
edges and nodes. Finding small subgraphs or minors that preserve or approximate the distances
among a given subset of k nodes have been studied for planar graphs [22, 31, 33, 42, 43, 52, 53,
56, 72, 73] and for general graphs [1, 2, 24–26, 36, 38, 61, 64, 65, 80, 83, 96]. Such compressions
are appealing algorithmically, since we can readily feed them into our usual graph algorithms,
and recent research suggests that, in many settings, near-optimal compression bounds can be
achieved using such sparsifiers (e.g. when compressing general graphs with additive error [1, 3]).
A discouraging lower bound of Krauthgamer, Nguyen, and Zondiner [72] shows that even in
the case of unweighted grid graphs, it is impossible to beat the naïve bound using a (possibly
weighted) minor. Thus, a positive answer to Open Question 1 will have to involve a more
complicated data structure.
Labelling Schemes. An appealing way to represent graphs is to assign a label `v to each
node v, so that by looking at the labels of two nodes `s , `t we can infer certain properties such
as the distance between them dps, tq. Finding so-called distance labelling schemes in which the
labels are as short as possible is a classical subject of study [48, 54, 62, 82]. Such labels are used
for efficient algorithms both in theory [8, 89] and practice [40]. An inspiring lecture by Stephen
Alstrup at HALG 2016 surveys breakthroughs [16, 17, 19] achieved in this field in the last few
years, all of which involve shaving constants or logarithmic factors. A famous open question is
to close the rare polynomial gap in the bounds for planar graphs that has been embarrassingly
open since the work of Gavoile et al. [48]: the upper bound is Opn1{2 q bits per label (due to [51]
who shaved a log factor over [48]), and the lower bound is Ωpn1{3 q. The only known technique
to prove polynomial lower bounds1 is to argue that labelling schemes are one way to compress
graphs, and then use facts about the limits of graph compression. For example, the lower bound
for distance labelling of planar graphs [48] follows because labels of size Opn1{3´ε q can be used
to solve the metric compression problem using Opk ¨ n1{3´ε q bits, which contradicts the lower
1

The only result that somewhat deviate from this technique are 1.008 log n lower bound for nearest common
ancestors in trees [18] and 1{8 log2 n lower bound for distance in trees [17, 48]. The gist of both of them is being
able to argue about how much information can be shared by labels of two nodes. If the graph is not a tree, this
seems very challenging.

3

bounds above. In fact, the tight lower bound for metric compression of weighted planar graphs
leads to a tight lower bound for labelling schemes [4, 48]. Thus, to prove a tight lower bound
of Ωpn1{2 q for labelling schemes in unweighted planar graphs, the only approach we have with
current techniques is to negatively resolve Open Question 1, e.g. by accomplishing Challenge 1.
Routing and Dynamic Algorithms. A compact routing scheme assigns names and tables
to the nodes of a graph, so that each node s can find out the first edge on the shortest path
(or some approximate path) to any target node t only using the name of t and the local table
stored at s. There is a vast literature on the topic, seeking the best possible tradeoff between
sizes of the tables and the stretch in many different graph families (we refer the reader to Peleg’s
book [81] and the extensive surveys [46,47]). For planar graphs, Abraham, Gavoille, and Malkhi
[9] write: “Surprisingly, for stretch 1, the complexity of the size of the routing tables is not
?
known.” A simple upper bound is Õpn ¨ nq total table size, and an adaptation of the same
Gavoille et al. construction gives a lower bound of Ωpn ¨ n1{3 q [9]. It is likely that accomplishing
Challenge 1 would resolve this gap as well. Yet another problem with similar state-of-the-art
is the All Pairs Shortest Paths problem in dynamic planar graphs. Here, the goal is to have a
data structure that supports efficient updates to the graph (edge additions or removals), and
can answer shortest path queries efficiently. The breakthrough algorithm of Fakcharoenphol
and Rao [45], and the later optimizations [49, 59, 63, 70], achieve Õpn2{3 q time for updates and
queries. The only framework for showing polynomial lower bound was recently proposed by
Abboud and Dahlgaard [4] who proved a lower bound of n1{3´op1q under the popular APSP
Conjecture [5–7, 39, 84, 85, 95]. Using their framework, accomplishing Challenge 1 directly leads
to a higher lower bound of n1{2´op1q , as is known in the weighted case.
History suggests that weighted planar graph metrics might be harder to work with, but they
are never truly harder. In so many cases, a new algorithm for the unweighted case is followed
by an almost-as-good algorithm for the weighted case, a few years later. For example, a PTAS
for the Travelling Salesman Problem in the unweighted planar metric was found in 1995 [55],
and then for the weighted case in 1998 [21]. Perhaps it is only a matter of time until our lower
bounds for the unweighted metric match the weighted.

1.1

Our Results

Our first result is a new compression scheme for the planar graph metric, which achieves the
information theoretically best possible bit complexity, up to log-factors. We give a positive
resolution to Open Question 1, deem Challenge 1 to be infeasible, and show that unweighted
planar graphs are inherently less complex than weighted ones; in fact, they admit a polynomially
more efficient metric compression.
Theorem 1.2. Given an unweighted undirected planar
? graph on n nodes and a subset S of k
nodes, we can return a binary encoding of length Õp k ¨ nq from which all pairwise distances in
S can be recovered exactly.
This shrinks the gap in our understanding of the planar metric compression problem from
polynomial to polylogarithmic (removing this polylogarithmic gap remains an open question).
?
For comparison, when k “ n, we show that Θ̃pn3{4 q bits are necessary and sufficient, while in
the weighted case the bound is Θ̃pnq. Our encoding breaks the lower bound of Krauthgamer et
al. [72] for compressions using minors, and raises the question whether it can be matched via
other forms of sparsification or graphical compressions.
It is unclear whether our new compression scheme will lead to improved upper bounds for
labeling, routing, or dynamic algorithms. In Section 6, we discuss the difficulty in turning it
4

into a labelling scheme. Still, it certainly shakes our beliefs about the right bounds for those
problems. Even if better upper bounds are not possible, it is no longer a mere puzzle as in
Challenge 1 that is standing in the way of higher lower bounds – substantially new techniques
and frameworks must be developed.
Distance Oracles. Our first result was a mathematical advance in the understanding of the
planar graph metric. Next, we use it algorithmically to achieve a new Subset Distance Oracle
that could be an appealing choice in many applications.
A distance oracle is an encoding of a graph from which a pairwise distance can be queried
efficiently. Since the seminal paper of Thorup and Zwick [90], a central subject of study in
Graph Algorithms has been to understand the inherent tradeoff between the parameters of
these distance oracles (see the survey by Sommer [87]): The size of the compression, the query
time for returning a distance, the error in the answers, the preprocessing time to construct the
compression, and so on.
Many exact distance oracles for planar graphs have been proposed [20,29,41,45,79,97], mostly
focusing on the tradeoff between space and query time, and giving OpSq space and Opn2 {Sq query
time [76]. Cohen-Addad, Dahlgaard, and Wulff-Nilsen [35] show that the technique of abstract
Voronoi diagrams recently introduced into the field of planar graphs by Cabello [30] leads to an
oracle with Opn5{3 q space and Õp1q query time, suggesting that a better tradeoff is possible.
To get even better tradeoffs we might allow p1 ` εq error [66, 70, 88]: we can achieve very
small p1 ` δqn space and fast Õp1q query time. Note that opnq space is impossible in this setting,
no matter what query time we allow. However, another natural way to get better tradeoffs is
to restrict our attention to a subset of the nodes. A Subset Distance Oracle is a small space
data structure that can efficiently return the distance between any pair of nodes from a set S
?
of k nodes. Here, for any k “ opnq, e.g. k “ n, our new compression scheme suggests that a
distance oracle might have opnq space.
Subset distance oracles arise naturally. In typical applications of distance oracles, one can
predict that all queries will be among a subset of k “ opnq nodes. Space efficiency is often a
high priority. For example, if our graph is the national road network, one might be interested
in a mobile app that can return the distance between any pair of bus stops.
Our second result is the first subset distance oracle with non-trivial space bounds. Notably,
all previous distance oracles in the literature work equally well for weighted and unweighted
graphs, while ours uses new techniques that are provably impossible for weighted graphs.
Theorem 1.3. Given an unweighted undirected planar graph on n nodes and a subset
S of k
?
nodes, there is a polynomial-time algorithm that returns a data structure X of size Õp k ¨?nq such
that given X and any pair of nodes in S we can return the exact distance in Õpmintn3{4 , k ¨ nuq
time.
The main open question left by our work is whether our query time can be improved, perhaps
all the way down to Õp1q. This would be an essentially optimal distance oracle. But even as
it is, our query time is sublinear, and our space is sublinear for any k “ opnq, making it an
appealing choice in applications with strict space constraints.
Finally, an intriguing and wide open question is to extend (any of) our upper bounds to
directed planar graphs. Can we accomplish Challenge 1 if we allow directed edges? Our tools
heavily rely on the graph being undirected, yet it remains unclear if a higher lower bound can
be proven for directed graphs.

5

1.2

Technical Overview

We exhibit the first use of the Unit-Monge property to the algorithmic study of planar graphs.
It is well known that distances in a planar graph enjoy this property, due to the non-crossing
nature of shortest paths in the plane, but prior to our work, only the (non-unit) Monge property,
was known to be algorithmically exploitable for planar graphs. For the past few decades, it has
been heavily utilized in numerous algorithms for problems related to shortest paths or minimum
cuts in planar graphs (e.g. [27–30, 45, 50, 59, 63, 69, 74–77]), and beyond, in dozens of papers
on computational geometry (e.g. [11–15, 50, 63, 67]) and pattern matching (e.g. [37, 57, 86,
92]). Meanwhile, the stronger Unit-Monge property has only been exploited for algorithms on
sequences where it has already led to several breakthroughs. We refer the reader to the 159-page
monograph of Tiskin [91] for an exposition of these applications.
Recall that we want to encode the distances among k nodes in a planar graph. Let us assume
that we are lucky and all the nodes lie on a single face of the graph. Denote the nodes appearing
on the face in order s1 , . . . , sk{2 , t1 , . . . , tk{2 , and for simplicity assume that we only want to
encode si -to-tj distances. Let M be the k{2 ˆ k{2 matrix of distances so that M ri, js “ dpsi , tj q.
This matrix has the Monge property: For any i, j we have that M ri ` 1, js ´ M ri, js ď M ri `
1, j ` 1s ´ M ri, j ` 1s. This is because the si -to-tj shortest path and the si`1 -to-tj`1 shortest
path must cross. Moreover, it is Unit-Monge, that is, M ri ` 1, js ´ M ri, js P t´1, 0, 1u. This
is because there is an edge between si and si`1 and so the distances involving these nodes are
always at most 1 apart.
Our gains come from the fact that Unit-Monge matrices are compressible into Opk log kq bits!
For non-unit Monge matrices, the construction of Gavoille et al. implies an Ωpk 2 q lower bound.
Another striking example for the extra power of the Unit-Monge property is the fact that (a
compact representation of) the distance product of two n ˆ n such matrices can be computed
in Opn log nq time [92], while for non-unit Monge matrices only Opn2 q algorithms are possible.
The main issue for us, and in general when exploiting Monge properties, is that the nodes
we care about do not necessarily lie on a cycle. The simple solution is to add a cycle connecting
our k nodes and assign weight `8 to the new edges so that they do not change the distances,
or more formally, to triangulate the graph. After we do this, we have the Monge property, but
because of the infinite weight edges, we do not have the unit-Monge property. This solution is
common to all the algorithms cited above that use the Monge property, and is quite reasonable
when the graph is weighted to begin with. For unweighted graphs, on the other hand, our work
proves that it is too lossy and a more involved solution leads to much better results.
At a very high-level, our approach is to use a Baker-like decomposition into slices (vertices at
consecutive levels of some specific BFS tree) whose boundaries are cycles, and to store distances
to the slice boundaries. Observe that when we argued above that the unit Monge property
holds because there is an edge between si and si`1 , we did not require that there is also an
edge between tj and tj`1 . In our solution there is an edge between consecutive vertices on the
boundary cycle of each slice. Therefore, even if we triangulate each slice using infinite weight
edges, we can still exploit the unit Monge property when storing distances between certain
vertices in a slice and the slice boundary.
The decomposition into slices is such that, after triangulation, the slices have small cycle
separators. We recursively separate the vertices of the set S within each slice using small cycle
separators. We store distances between separators and the slice boundary (using the unit Monge
property) and between vertices of S and separators (using the fact that separators are small).
Significant technical issues arise with the nesting structure of slices. This gives rise to so-called
holes in a slice. Dealing with multiple holes requires a detailed study of additional structural
properties, and a more complicated recursive solution based on these properties. In essence, we

6

show that whenever a naïve solution does not work in the presence of multiple holes, there is
one hole that can be handled efficiently using a different approach.
We believe it is very likely that other problems in unweighted planar graphs can be solved
by exploiting the Unit-Monge property. Our near-optimal metric compression serves as a proof
of concept that this is possible. However, technical challenges might have to be overcome in
each specific application. In particular, the fast distance product algorithm for unit-Monge
matrices [92] appears to be a strong and relevant technique that we are so far unable to exploit
for solving problems in planar graphs.

2

Preliminaries

We assume basic familiarity with planar graphs and planar graph duality. We denote the primal
graph by G and the dual graph by G˚ . For a spanning tree T of G, we use T ˚ to denote the
spanning tree of G˚ . It is well known [94] that the set of edges of G not in T form a spanning
tree T ˚ of G˚ . We often refer to T ˚ as the cotree of T [44]. For a spanning tree T of G and
an edge e of G not in T , the fundamental cycle of e with respect to T in G is the simple cycle
consisting of e and the unique simple path in T between the endpoints of e.
Given an assignment of nonnegative weights to the faces of G, we say that a simple cycle C
is a balanced separator if the total weight of faces strictly enclosed by C and the total weight
of faces not enclosed by C are each at most 5{6 of the total weight.2 We often assign weights
to vertices rather than to faces. Finding a balanced separator with respect to vertex weights
reduces to the case of face weights (for each vertex, simply remove its weight and add it to an
incident face). It is well known (see, e.g., [71]) that in triangulated planar graphs there exists a
balanced separator that is a fundamental cycle assuming that no face has more than 1{2 of the
total weight (in fact, this is true for any planar graph such that T ˚ has maximum degree 3). For
vertex-weights, if no vertex has more than 1/2 of the total weight and the graph is triangulated
and there are no self loops then by evenly transferring the weights to faces we obtain that no
face receives more than 1/2 of the total weight (because every node is incident to at least two
faces) and we can invoke the face-weights version of the balanced separator. Many planar graph
algorithms triangulate the graph by adding edges to ensure that short balanced cycle separators
exists. The lengths of the added edges is set to be sufficiently large so as not to change distances
in the graph. This is clearly not possible in unweighted planar graphs, and is one of the obstacles
we will need to overcome.

2.1

The Monge and Unit-Monge properties

One of the main tools we use for succinct representation of distances in unweighted undirected
planar graphs is the unit Monge property. We next prove a sequence of lemmas that utilize
this property to efficiently store distances between vertices on cycles. We begin with encoding
distances between disjoint sets of vertices on a single face (Lemma 2.1), then encoding all-pair
distances between the vertices on a single face (Lemma 2.2), then encoding all-pair distances
between the vertices on a single simple cycle (Lemma 2.3), and finally, encoding the distances
between the vertices of two faces (Lemma 2.4).
Lemma 2.1. Let C “ pv1 , v2 , . . . , v|C| q be the cyclic walk of a face of a planar graph partitioned
into two parts C1 “ pv1 , v2 , . . . , v` q and C2 “ pv``1 , v``2 , . . . , v|C| q. Then, for any subset C21 of
C2 , all distances between vertices of C1 and vertices of C21 can be encoded in Õp|C1 | ` |C21 |q bits.
2

It is more usual to require that the total weight is at most either 2{3 or 3{4. However, in our particular
application 5{6 turns out to be more convenient.

7

Proof. Let C21 “ tvp1 , vp2 , . . . , vps u. We define an ` ˆ s matrix M such that M ri, js equals the
distance in G between vi and vpj . The matrix M is Monge, that is
M ri ` 1, js ´ M ri, js ď M ri ` 1, j ` 1s ´ M ri, j ` 1s
for any i P r1, ` ´ 1s and j P r1, s ´ 1s. This is because the shortest vi -to-vpj and vi`1 -to-vpj`1
paths must necessarily cross. Furthermore, the matrix M is unit-Monge, that is
M ri ` 1, js ´ M ri, js P t´1, 0, 1u
for any i P r1, ` ´ 1s and j P r1, ss, because there is an edge pvi , vi`1 q. Consequently, for any
i P r1, ` ´ 1s, the sequence of differences M ri ` 1, js ´ M ri, js is nondecreasing and contains only
values from t´1, 0, 1u, so can be encoded by storing the positions of the first 0 and the first
1. Storing these positions for every i P r1, ` ´ 1s takes Õp`q bits. To encode the whole M , we
additionally store M r0, js for every j P r1, ss using Õpsq bits.
Lemma 2.2. Let C “ pv1 , v2 , . . . , v|C| q be the cyclic walk of a face of a planar graph. Then, all
distances between vertices of C can be encoded in Õp|C|q bits.
Proof. We recursively encode all distances between vertices from a contiguous fragment of C
using Lemma 2.1. We start with the whole v1 , v2 , . . . , v|C| . To encode the distances between all
vertices vi , vi`1 , . . . , vj , where i ă j, we set m “ tpi ` jq{2u and proceed as follows:
1. Recursively encode the distances between all vertices vi , vi`1 , . . . , vm .
2. Recursively encode the distances between all vertices vm`1 , vm`2 , . . . , v|C| .
3. Apply Lemma 2.1 with C1 “ pvi , vi`1 , . . . , vm q and C21 “ tvm`1 , vm`2 , . . . , vj u.
The total size of the encoding is described by the recurrence T psq “ Õpsq`2T ps{2q, hence solves
to Õp|C|q.
Lemma 2.3. Let C “ pv1 , v2 , . . . , v|C| q be a simple cycle in a planar graph. Then, all distances
between vertices of C can be encoded in Õp|C|q bits.
Proof. Consider the two planar graphs Gout (Gin ) obtained by removing all vertices enclosed (not
enclosed) by C. C is the cyclic walk of a face in Gin and Gout , hence we can apply Lemma 2.2
to store the distances in Gout and in Gin between vertices of C. This is enough to encode the
distances in G between vertices of C, as any such shortest path can be partitioned into shortest
paths between two vertices of C such that each of these paths exists in either Gin or Gout .
Lemma 2.4. Let Cext “ pv1 , v2 , . . . , v|Cext | q and Cint “ pu1 , u2 , . . . , v|Cint | q be the cyclic walk of
1
two faces of a planar graph. Then, all distances between a prefix Cext
of Cext and any subset
1
1
1
Cint of Cint can be encoded in Õp|Cext | ` |Cint |q bits.
1 and C
Proof. We first choose a shortest path P between Cext
int and let vi and uj be its endpoints.
1
We make an incision along P and apply Lemma 2.1 to encode the distances between Cext
and
1
1
1
Cint corresponding to shortest paths that do not cross P using Õp|Cext | ` |Cint |q bits of space.
It remains to encode distances corresponding to shortest paths that do cross P . Without loss of
generality P connects v1 and u1 . We orient Cext and Cint so that after making an incision along
P the vertices v2 and u2 are adjacent to the endpoints of P .
Consider a shortest path P 1 from vi to uj crossing P , see Figure 1. Because both P and P 1
are shortest paths, P 1 can be assumed to cross P exactly once. Similarly, a shortest path P 2
from vi`1 to uj`1 crossing P can be assumed to cross P exactly once. We claim that P 1 must

8

Cext
Cint

P 00

vi+1

uj+1
uj

u1

0
vi P

P
v1

Figure 1: The Monge property in Lemma 2.4.
cross P 2 . Otherwise, by considering an incision along P 1 we can conclude that P 2 crosses P an
even number of times but this is a contradiction. Therefore, any such P 1 and P 2 must cross.
This means that the matrix M , where M ri, js is set to be the length of a shortest path between
vi and uj crossing P once, is Monge. That is,
M ri ` 1, j ` 1s ` M ri, js ě M ri ` 1, js ` M ri, j ` 1s.
Additionally, M ri, js ´ M ri ` 1, js P t´1, 0, 1u because pvi , vi`1 q is an edge. We can hence apply
1 | ` |C 1 |q bits.
the reasoning from Lemma 2.1 to encode M using Õp|Cext
int

3

The Encoding

Our encoding is based on decomposing the input graph G into slices. To define the slices, recall
the face-vertex incidence graph F V pGq of a planar graph G: It has a vertex for every vertex v
of G and a vertex for every face f of G, and if a vertex v of G is incident to a face f of G then
there is an edge between their corresponding vertices in F V pGq.
We run a breadth-first search in F V pGq, starting from the node representing the infinite
face of G. After every even number of steps, the yet unexplored part of the graph can be
decomposed into a number of connected components, the boundary of each being a simple cycle.
More formally, we assume that the infinite face of G is a triangle by enclosing the whole graph
in a triangle, which is connected to one of the original vertices with a single edge. We define
the level of a face f or a vertex v of G to be its depth in the BFS tree of F V pGq. Thus, e.g.,
the level of the infinite face of G is zero, and the level of the vertices incident to the infinite face
of G is 1. For each even integer i ě 2, we define Kěi to be the set of connected components of
the subgraph of G induced by the faces with level at least i. We call each component K P Kěi
a level-i component. We use a tree K called the component tree of G to capture the nesting of
level components. The nodes of K are the level components of G. A level component K is an
ancestor of a level component K 1 in K if the set of faces in K contains the set of faces in K 1 .
Since we assume that the infinite face of G is a simple triangle, K is indeed a tree whose root is
the component corresponding to the set of all faces of G except for the infinite face.
The boundary of a component K is the set of edges that are incident to a face in K and to a
face not in K. It is not difficult to see that the boundary of each component K is a simple cycle
in G, and that the boundaries of different components are edge-disjoint. See [68, 71] for these
9

and other properties of components and the component tree. For a node k P K, we associate k
with the boundary cycle Ck of the level component represented by k, and define the cost of k
denoted costpkq to be the length of Ck . For example, for the root r of K we have that Cr is a
triangle and that costprq “ 3.
Lemma 3.1. For any w ě 1, there exists δ P r0, wq such that the total cost of all nodes of K at
depth δ, δ ` w, δ ` 2w, . . . is Opn{wq.
ř
Proof. vPK costpvq “ Opnq because cycles corresponding to the nodes of K are pairwise edge
1 q “ H for
disjoint. Let
of all nodes of K at depth δ, δ`w, δ`2w, . . .. Then SpδqXSpδ
řSpδq consist
ř
ř
1
δ ‰ δ and δPr0,wq vPSpδq costpvq “ Opnq, so there exists δ P r0, wq such that vPSpδq costpvq “
Opn{wq as claimed.
To define the slices we apply Lemma 3.1 and call the nodes of K at depth δ, δ ` w, δ ` 2w, . . .
marked. The root of K is also marked. Then, for every marked node v P K, the slice of v is
the subgraph of G enclosed by Cv and not strictly enclosed by Cu for any marked descendent
u of v. The embedding of slices is inherited from the embedding of G. Thus, the boundary of
the infinite face of the slice s of v is Cv . The cycle Cv is also called the boundary of the slice s.
Each cycle Cu corresponding to a marked descendant u of v such that there are no other marked
nodes on the v-to-u path becomes a face in the slice s. Such a face is called a hole of s, and
Cu is called the boundary of the hole. Note that, by definition, Cu is the boundary of the level
component that is embedded in the hole u. Because the total cost of all marked nodes is Opn{wq
and the cost of the root is 3, the total size of all boundaries in all slices is Opn{wq. Additionally,
by construction, for any slice s, a breadth-first search of F V psq, the face-vertex incidence graph
of s, starting at the infinite face of s, terminates after Opwq iterations and every hole is a leaf
in the obtained breadth-first search tree.
By definition of slices, each slice contains faces and vertices at Opwq consecutive levels. We
would like to use in our solution short (i.e., Opwq) fundamental cycle separators within each
slice. However, the diameter of a slice is not necessarily Opwq because face sizes may be large.
To deal with this issue we triangulate the faces so that a BFS tree of a slice will have depth
Opwq, and will be consistent with the BFS tree of F V psq.
Lemma 3.2. We can triangulate all faces of a slice s so that a BFS starting from the external
face produces a spanning tree Ts with the property that vertex v is the parent of vertex u in Ts if
and only if v is the grandparent of u in the BFS tree of F V psq.
Proof. Let TF V be the BFS tree of F V psq. If v and u are incident to the same face in s, and
v is a grandparent of u, and vu is not an edge in s, we add vu as an artificial triangulation
edge to s. Adding these edges can be done consistently with the embedding of s because the
path in TF V can be embedded on the same plane as s such that s and TF V only intersect at
vertices of s. See Figure 2. We introduce an artificial vertex vs embedded in the infinite face
of s and triangulate the infinite face of s by adding edges between vs and every vertex of the
infinite face of s. Similarly, we triangulate each hole h of s by introducing an artificial vertex
vh , embedded in h, and adding edges between vh and every vertex on the boundary of h. Any
remaining non-triangulated faces can be triangulated arbitrarily. Since for every grandparent
to grandchild path in TF V there is a corresponding edge in the triangulation of s, there exists
a BFS tree Ts rooted at the artificial vertex vs that satisfies the statement of the lemma. Note
that all the artificial vertices embedded in holes of s are leaves of Ts , and hence satisfy the
statement of the lemma vacuously.
Let s1 be the graph obtained from the slice s after applying Lemma 3.2. Let Ts be the
BFS tree of s1 . Note that, any fundamental cycle C w.r.t. Ts consists of two paths in Ts , each
10

Figure 2: Triangulating a slice. The vertices and edges of a slice s with two holes are shown in
solid black. In this example w “ 2. Edges of TF V , the BFS tree of F V ps) are shown in double
red lines. Only some of the edges of TF V are shown to avoid clutter. Artificial triangulation
edges are shown in dashed gray. The BFS tree Ts of the triangulation of s is shown in blue.
consisting of Opwq vertices due to the triangulation. However, C may use edges that are not
original edges of s (i.e., artificial triangulation edges). We do not want to consider such edges
when dealing with distances, because distances in s1 differ from distances in s. To this end we
use the notion of a Jordan curve. A Jordan curve in s is an embedded curve that intersects the
embedding of s only at vertices of s. Since the embedding of the triangulation s1 is consistent
with that of s, each path in Ts is a Jordan curve in s. We say that Ts is a Jordan tree in s. In
particular, any fundamental cycle w.r.t. Ts is a Jordan cycle (closed Jordan curve) in s. We next
describe how the tree Ts can be used to recursively decompose s into subgraphs called regions.
A region R is a subgraph of s. The boundary of R is defined as the set of vertices of R
that are incident (in G) to both an edge in R and to an edge not in R. Thus, for example, the
boundary of the region consisting of the entire slice s consists of the external boundary Cext
of s and of the boundaries of all the holes of s. Let R be a region. Let C be a fundamental
cycle w.r.t. Ts . The tree Ts may contain edges that are not edges of R (either because they are
triangulation edges, or because they are edges of s that do not belong to the region R). Since
the embedding of Ts is consistent with the embedding of any subgraph of s, C is a Jordan cycle
in R. The operation of separating R using C yields two subgraphs. One is the subgraph induced
by the faces of R strictly enclosed by C and the other is the subgraph induced by the faces of
R not strictly enclosed by C. This view of Ts as a Jordan tree in any region allows us to reuse
the same tree Ts throughout the recursive decomposition.
This recursive process can be described by a binary tree Ts . Each node v of Ts corresponds
to a region (subgraph) Rv of s. The root of Ts is the entire slice s. Each non-leaf node v of Ts
is associated with a (Jordan) fundamental cycle separator of Ts , which we denote Sepv . The
regions of the two children of v are the regions obtained by separating Rv with the Jordan cycle
Sepv .
11

3.1

The simplified case of a single hole

We begin with the simplified case, in which we assume that each slice has a single hole. This is
the case, for example, when the input planar graph is a grid (with possibly subdivided edges).
First we use Lemmas 2.3 and 2.4 to store, for each slice s with external boundary Cext , and a
single hole h with external boundary Ch the following distances. The boundary-to-boundary
distances: the distances (in s) among the vertices of Cext , and the hole-to-boundary distances:
the distances (in s) between the vertices of Cext and the vertices of Ch .
Boundary-to-boundary and hole-to-boundary distances encode distances “between slices”.
We also need to encode distances “within slices”. We will use the fact that s has a spanning
tree of depth Opwq to decompose s into regions, each containing a single distinguished node
(i.e., node of S), and having a boundary that consists of Opwq vertices. Then we can afford
to store, for each distinguished node, its distance to the boundary of its region, and, using the
unit-Monge property, to also store the distances between the Opwq vertices on the boundary of
each region R to the vertices of Cext and Ch (i.e., the boundary of s) that belong to R. These
distances will suffice for reconstructing the distance between any pair of distinguished nodes.
Let Ss denote the set of distinguished vertices in slice s. We use fundamental (Jordan) cycle
separators w.r.t. the tree Ts to recursively divide s into regions, until each region contains a
single distinguished vertex. At each recursive step we separate a region R into two subregions
by choosing a fundamental cycle separator w.r.t. Ts that balances the number of distinguished
vertices in R (i.e., assigning unit weight to each distinguished vertex in R and zero weight to all
other vertices). Note that, since we use balanced separators, the depth of the recursion tree Ts is
Oplog |Ss |q “ Oplog nq. Recall that the fundamental cycle separators w.r.t. Ts do not cross each
other, and, by construction of Ts in Lemma 3.2, each fundamental cycle separator crosses each
of the external boundary of s and the hole of s at most twice. Therefore, the boundary of each
region Rv corresponding to a node v in the recursive decomposition tree Ts contains Oplog nq
vertex disjoint maximal subpaths of Cext , and Oplog nq vertex disjoint maximal subpaths of Ch .
At the step of the recursive decomposition corresponding to node v P Ts with separator Sepv
and two children u, w, we store S-to-separator distances: explicitly store the distances (in Rv )
between every vertex of S in Rv and every vertex of Sepv , separator-to-boundary distances
and separator-to-hole distances: for i P tu, wu, the distances (in Ri ) between every vertex
of Sepv and every maximal subpath of Cext or Ch on the boundary of Ri , using Lemma 2.1 or
Lemma 2.4 (depending whether they lie on a single or two faces of Ri ). Finally, for every leaf
v P Ts , we store S-to-boundary distances and S-to-hole distances: the distance between the
unique distinguished vertex in Rv to every vertex of Cext or Ch on the boundary of Rv .
?
Analysis. We first show that the total space is Õp k ¨ nq, and then show that the distances
between any pair of vertices in S can be recovered using just the information we stored. Since
the total size of all slice boundaries is Opn{wq, storing the boundary-to-boundary distances and
the hole-to-boundary distances takes Õpn{wq using Lemmas 2.3 and 2.4. Since the depth of Ts
is Oplog nq, each vertex of Ss belongs to Oplog nq regions in the decomposition of s. Since, in
addition, |Sepv | “ Opwq for every v P Ts , the total space required for storing the S-to-separator
distances is Õpk ¨ wq. Consider a region R of a slice s. Recall that the vertices of Cext (Ch ) that
belong to R lie on Oplog nq vertex disjoint maximal subpaths of Cext (Ch ). The endpoints of
each such maximal subpath may belong to another region R1 at the same depth in Ts . Therefore,
R shares Oplog nq vertices of Cext (Ch ) with other regions at the same depth in Ts . Finally, recall
that the number of regions of s is Õp|Ss |q. Therefore, using Lemma 2.1 or Lemma 2.4, the total
space for storing the separator-to-boundary and separator-to-hole distances is Õpn{w `k `k ¨wq.
In more detail, let ci be the total number of slice/hole boundary vertices in the i-th slice. Then, in

12

every slice every boundary/hole vertex that is not an endpoint of a maximal subpath contributes
at most once at each level of recursion. At each level, we have at most k recursive calls, so at
most Opk log nq maximal
subpaths and at most k fundamental cycle separators. Therefore, the
ř
total space is Opp i ci ` k log n ` k ¨ wq log nq “ Õpn{w ` k ` k ¨ wq. Storing S-to-boundary
distances and S-to-hole distances at the leaves of the recursion tree requires total Õpk ` n{wq
bits since each boundary or hole vertex belongs to exactlya
one leaf region, except for Opk log nq
vertices (endpoints of maximal subpaths). Choosing w “ n{k proves the space bound.
Finally, we prove that the distances between any pair of vertices in S can be recovered using
just the information we stored. For any x, y P S, if a shortest x-to-y path does not leave s then
x, y P Ss , and the distance can be obtained using the S-to-separator distances stored in the
lowest common ancestor of the regions of x and y in Ts . Otherwise, let P be a shortest path
between vertices x P Ss1 and y P Ss (where s1 is either s or, wlog, enclosed by the hole of s).
Let P ri, js denote the subpath of P between vertices i and j. Let v be the first vertex of P
that belongs to the boundary of s1 or to the boundary of a hole of s1 . If P rx, vs contains some
vertex of a fundamental cycle separator used in processing s1 , let u be the last vertex of P that
belongs to the earliest such separator. If u does not exist, then the length of P rx, vs is stored
as an S-to-boundary or an S-to-hole distance. If u exists then the length of P rx, us is stored
as a S-to-separator distance, and the length of P ru, vs is stored as a separator-to-boundary or
separator-to-hole distance. Let w be the last vertex of P that belongs to the boundary of s. The
length of P rv, ws can be computed from boundary-to-boundary and hole-to-boundary distances
since P rv, ws can be decomposed into subpaths between boundary vertices of slices. The length
of the suffix P rw, ys can be computed in a similar manner to that of the prefix P rx, vs.

3.2

The general case

A difficulty that arises in the presence of multiple holes is that since the number of holes is not
bounded by a constant, we cannot afford to store distances involving holes. For example, storing
hole-to-boundary distances between the external boundary Cext of a slice s and the boundary
of each hole of s requires Ωp|Cext |q “ Ωpn{wq bits per hole. Since the number of holes can be
Ωpnq, the total space could be Ωpn2 {wq.
The role of storing distances involving boundaries of holes was to allow the recovery of
distances to distinguished vertices enclosed in these holes. We modify our approach for processing
a slice s to take into account the distinguished vertices enclosed in holes of s as well as the
distinguished vertices in s itself. As in the single hole case, the slice s will be recursively divided
using fundamental cycle separators. For any region R encountered along the recursive process,
let S R denote the subset of the distinguished vertices in R, as well as those enclosed by any
hole in R. Thus, for example, S s is the set of all vertices in S that are enclosed (in G) by the
external boundary of slice s. We say that a Jordan cycle separator C of a region R is good if it is
balanced w.r.t. S R and does not go through any hole of R. The problem with Jordan separators
that go through some hole h is that they partition the distinguished vertices enclosed by h in
an unspecified way since these distinguished vertices are not represented in R. It is not hard to
see that if a good separator always exists then we do not need to store any distances involving
holes.
In reality we cannot always find a good separator. Consider, for example, the case where some
hole h of a region R encloses most of the vertices of S R . Clearly, a separator that is balanced
w.r.t. S R must go through h. Thus, there is no good separator in such a case. We show,
however, that we can always either find a good separator, or there exists some hole (which we
call a disposable hole) that can be dealt with in a special way. This is reminiscent of recursive
procedures based on heavy path decomposition, where heavy nodes (disposable holes in our

13

case) are treated differently than light ones. We guarantee that, in either case, each resulting
subregion contains only a constant fraction of S R , so the depth of the recursion is Oplog nq. We
next explain the details.
Good separators and disposable holes. Let R be a region. We define the weight of each
vertex v of R to be 1 if v is a distinguished vertex. For each hole h of R, we define the weight of
the artificial vertex vh embedded in h to be the number of distinguished vertices strictly enclosed
(in the whole graph G) by the boundary of h. All other vertices are assigned weight zero.
Recall that a cycle separator is good if it does not go through any hole. We would like to
separate R using a good fundamental cycle separator Ce of some edge e w.r.t. Ts . If we can find
such separator Ce where e is not incident to vh for some hole h, then Ce is a good separator
(since the vertices vh are leaves of the spanning tree Ts ). Otherwise, we must separate R with a
fundamental cycle separator that goes through holes. We next define disposable holes, and then
show that we can allow the fundamental cycles to go through such holes.
Let k be a node (level component) in K. Let Ck be the boundary cycle of k. Let e be an
edge of Ck . Note that e R Ts . This is because both endpoints e have the same level, so, by
Lemma 3.2, neither can be the parent of the other in Ts . Let f, g be the endpoints of e in the
dual graph, such that f is a face in k and g a face not in k. Since e R Ts , e is in the cotree
Ts˚ . Consider breaking Ts˚ into two subtrees by deleting e. We say that the edge e is light if
the subtree of Ts˚ that contains g has weight at most W {2 where W is the total weight of the
vertices of R. Note that we defined weights of primal vertices, whereas the vertices of Ts˚ are
primal faces. To define face weights, evenly redistribute the weight of each vertex among all
of its incident faces. There is an equivalent, primal view of light edges: The Jordan cycle Ce
partitions R into two subgraphs, exactly one of which contains the faces of the level component
corresponding to k. We say e is light if the weight of the subgraph that does not contain the
level component k is at most half the weight of R. We say that a level component k is disposable
in region R if there are boundary edges of k in R, and if every edge e of the boundary of k that
is also in R is light. Note that, in particular, this definition applies to holes (since holes are level
components). See Figure 3.
Before showing why disposable holes exist and that they are useful, we first mention a simple
property of Ts˚ and then use it to prove the existence of disposable holes.
Property 3.3. The cotree Ts˚ enters each level component exactly once.
Proof. The spanning tree Ts is monotone with respect to node levels. Thus, if e is an edge of the
boundary of a level component k, then one of the components of Ts˚ ze contains no other faces,
vertices or edges of k. See Figure 4 for an illustration.
Lemma 3.4. If a region R contains more than one vertex with non-zero weight, then there exists
either a good balanced fundamental cycle separator or a disposable hole in R.
Proof. Let W be the total weight of vertices in R. Consider the component tree K. Let u be
a deepest disposable component in K such that Cu has an edge in R. If u is a hole of R then
we found a disposable hole, and we are done. Otherwise, we next show that there exists a good
separator.
Let u1 , u2 , . . . , ud be the children of u in K (if there is no disposable component in R, then
define u to be R, Cu to be the external boundary of R, and let u1 , . . . , ud be the set of rootmost
components in K such that Cui has an edge in R). Since none of the ui ’s is disposable, for each
ui there exists exactly one boundary edge ei “ pfi , gi q (here we wrote ei as a dual edge, and fi is
the endpoint of ei that belongs to ui ), such that the subtree of Ts˚ zei that contains gi has weight
14

root of Ts

≤W/2

g

e

f

vh

Figure 3: An illustration of a region with a disposable hole. The edges of a boundary of a hole h
are shown in double-line grey. Since the boundary of a hole is a level cycle, none of the edges of
the boundary of h belongs to the spanning tree Ts (blue). The artificial triangulation vertex vh
of h and the triangulation edges (grey dashed) are shown. The cotree Ts˚ is shown in thin red.
Suppose that the number of distinguished nodes enclosed by h is at least W {2 (so the weight of
vh is at least W {2). Then, for any edge e of the boundary of h, the part of Ts˚ ze that does not
contain faces of h weighs at most W {2, so e is a light edge and h is a disposable hole.
at least W {2. Consider the following two phase process (see Figure 5 for an illustration): Let
T0˚ “ Ts˚ . If Ti˚ contains more than a single face of some uj (in which case it must contain all
˚ is obtained from T ˚ by rooting T ˚ at g and deleting all
faces of uj by Property 3.3), then Ti`1
j
i
i
˚
˚ is
the strict descendants of fj in Ti , so that fj becomes a leaf. The weight assigned to fj in Ti`1
˚
the total weight of all the vertices in the deleted subtree. Thus, the weight of Ti`1 remains W ,
and, by definition of ej , the weight of fj is at most W {2. The first phase terminates when Ti˚
contains at most one face (fj ) from each uj . In the second phase, while Ti˚ contains an edge e
˚ is obtained from T ˚ by rooting T ˚ at the endpoint
of Cu that is not a leaf edge of Ti˚ , then Ti`1
i
i
g of e that belongs to u, and deleting all the strict descendants of the other endpoint f of e in
˚ is set to the
Ti˚ , so that f becomes a leaf. Similarly to the first phase, the weight of f in Ti`1
total weight of all the vertices in the deleted subtree. Since u is disposable, the weight of f is
at most W {2.
Let Tt˚ be the resulting tree. Since Tt˚ contains at most one face from each ui , Tt˚ contains
no triangulation edges of a hole (both endpoints of a triangulation edge of a hole belong to
the hole). Furthermore, the total weight of Tt˚ is W , and every leaf of Tt˚ created during the
two phase process has weight at most W {2 (by definition). For the remaining nodes of Tt˚ , the
degree is at most 3 and the weight is also at most W {2, because the original weights in Ts˚
are at most W {2 (otherwise, the node corresponds to a hole of weight at least W {2 that is, by
definition, disposable, and we are done). Therefore, there exists an edge e whose deletion from
Tt˚ results in two trees, none of which weighs more than 5W {6. By construction of the weights
of Tt˚ , the balance of the fundamental cycle of e w.r.t. Ts is exactly the ratio of the weights of
the subtrees obtained by deleting e from Tt˚ . Therefore, the fundamental cycle Ce of e w.r.t. Ts
is a balanced Jordan cycle separator. Since no edge of Tt˚ is a triangulation edge of a hole, Ce
is a good separator.
With this structural lemma we can now describe our oracle. Consider a slice s and let
15

Figure 4: An example of the interaction between the spanning tree Ts (blue), the cotree Ts˚
(red), and boundary of level components (black cycles). Since Ts is monotone with respect to
levels, Ts˚ enters each level component exactly once.
Gs be the subgraph of G enclosed by the boundary of s. The goal of processing slice s is to
store information (distances) so that the following distances (in Gs ) can be recovered from the
information stored for all slices contained in Gs .
1. The distance between any two distinguished nodes in Gs ,
2. The distance between any distinguished node in Gs and any vertex on the boundary of s.
3. The distance between any two vertices on the boundary of s.
Encoding this information for all slices guarantees that distances between the distinguished
vertices in the whole graph are captured.
The encoding. To process a slice s, we first encode boundary-to-boundary distances: the
distances (in Gs ) between vertices on the boundary of s using Lemma 2.3. We then triangulate
s and define its spanning tree Ts using Lemma 3.2.
Next, we recursively separate s using fundamental cycle separators. The initial region R is
the entire slice s. Its boundary is the external boundary Cext of s. A region R is separated into
subregions obtained by cutting R along some fundamental cycle separator C w.r.t. Ts . Since
we only use fundamental cycle separators w.r.t. the same tree Ts , the separators never cross.
Hence, the boundary of each new region R1 consists of the contiguous portion of C that belongs
to R, and possibly portions of the boundary of R. Since C crosses Cext at most twice (at most
once for each of the two paths in the fundamental cycle C), the number of contiguous maximal
fragments of Cext in the boundary of R1 is at most one plus the number of such fragments in
the boundary of R. Consequently, the number of contiguous maximal fragments of Cext in the
boundary of any region is bounded by the depth of the recursion, which we will show is Õp1q.
We now explain how to choose the fundamental cycle separator C with which we separate
R. This is achieved using two interleaving recursive processes. We refer to the first one as the
outer recursion, and to the second one as the hole elimination recursion. In a step of the outer
recursion we apply Lemma 3.4.
If we find a good balanced fundamental cycle separator C, then we use it to separate the
region R. Every vertex in S R explicitly stores S-to-separator distances: its distance (in Gs )
to every vertex of C. In addition, for each subregion R1 , for each contiguous maximal fragment
16

e2

f2

e2

e1

f1

f1

Figure 5: Illustration of the process of constructing the cotree Tt˚ according to which a good
separator is found. Three level boundaries are shown (black cycles). The external one is Cu ,
the two cycles enclosed by Cu are Cu1 and Cu2 . The subfigures show the process of splitting
the cotree Ts˚ , first at e1 , then at e2 . In the second phase the cotree is further split at the two
remaining edges of Cu . The resulting tree Tt˚ is an induced subtree of Ts˚ in which a balanced
edge-separator can be found. Since none of the edges of Tt˚ has both endpoints in any ui , none
of the edges of Tt˚ are triangulation edges of a hole.
bi of Cext in R1 , we encode separator-to-boundary distances: the distances (in R1 ) between
bi and C using Lemma 2.1 or Lemma 2.4 (depending on whether the vertices of the separator
C and the vertices of bi lie on a single or two faces of R1 ). Then, we call the outer recursion
recursively for each subregion R1 . The outer recursion terminates when there is at most one
vertex with positive weight in the current region R. If the only remaining object is an artificial
vertex vh , we apply Lemma 2.4 to encode hole-to-boundary distances: the distances (in R)
between the boundary Ch of h and bi , for each contiguous maximal fragment bi of Cext in R. If
the only remaining object is a distinguished vertex u, we store S-to-boundary distances: the
distances (in Gs ) from u to every vertex of every bi . If the current region R contains no vertices
with positive weight, the outer recursion terminates.
If, on the other hand, we found a disposable hole h, we store hole-to-boundary distances:
distances between the boundary Ch of h and every contiguous maximal fragment bi of Cext
in R. The weight of the artificial vertex vh is set to zero. This reflects the fact that for the
rest of the processing of s, distinguished vertices enclosed by the hole h will not be treated
individually and directly, but rather by encoding distances involving the vertices of Ch . From
this point on, vertices of S inside h are no longer considered vertices of S R . We then call the
hole elimination process for the hole h in region R (see Figure 6). In a single step of the hole
elimination recursion, a region R is separated using a fundamental cycle separator C w.r.t. Ts
that is balanced w.r.t. the number of vertices of Ch in R (i.e., a weight 1 is assigned to each
vertex of Ch and 0 to all other vertices). Note that C is necessarily a fundamental cycle w.r.t.
Ts of some triangulation edge that is incident to vh . The boundary of each of the two resulting
regions contains a single contiguous portion of Ch consisting of roughly half the vertices of Ch in
R. Similarly to the single hole case, we store S-to-separator distances: distances (in Gs ) from
every vertex of S R to every vertex of C. For each subregion R1 obtained by separating R along
C, for each contiguous fragment bi of Cext in R1 , we encode separator-to-boundary distances:
the distances (in R1 ) between bi and C using Lemma 2.1 or Lemma 2.4, and separator-to17

vh

R0

R
e
vh

Figure 6: Illustration of the process of eliminating a disposable hole. A disposable hole h with
artificial vertex vh in a region R0 is shown in top-left. The spanning tree Ts is indicated in
blue. R0 is recursively separated using fundamental cycle separators that are balanced w.r.t. the
number of nodes of the boundary Ch of h. The elimination process finishes (bottom-left) when
the current region R contains only two consecutive vertices of Ch , which are the endpoints of
some edge e. This region R differs from the the region R1 obtained by separating R0 using the
fundamental cycle of e w.r.t. Ts by a single vertex (vh ).
hole distances: the distances (in R1 ) between C and the single contiguous fragment of Ch that
belongs to R1 using Lemma 2.1. We then apply the hole elimination process recursively to each
subregion R1 . It terminates when the current region R contains at most two consecutive vertices
of Ch , or when it contains at most one distinguished vertices. When this happens, we continue
with the outer recursion on R.
We next prove that the total depth of the entire recursive procedure is Oplog2 nq “ Õp1q.
Analyzing the recursion depth. We begin with the initial region R0 being the entire slice.
In a single step of the outer recursion, if we find a good separator then we use it to separate the
current region R0 thus decreasing the weight of each resulting region R by a constant factor.
If however we do not find a good separator, then we apply the hole elimination process on a
disposable hole h of the current region R0 . Since |Ch | “ Opnq, and since every recursive call
to the hole elimination process decreases the number of nodes of Ch by half, we get that after
Oplog nq recursive calls the hole elimination process terminates, with each resulting region R
containing only two nodes of Ch . Observe that these two nodes must be adjacent on Ch (see
Figure 6). Let e be the edge between them and let Ce be the fundamental cycle of e w.r.t.
Ts . Since h is disposable, the weight of the region R1 obtained by separating R0 using Ce is at
most half the weight of region R0 . Since R “ R1 Y tvh u and since the weight of vh is zero this
means that the weight of R is at most half the weight of R0 . We conclude that every Oplog nq
consecutive recursive calls the total weight of a region decreases by a constant factor. This shows
that the depth of the recursion is Oplog2 nq.

18

Correctness. We next prove that the distance between any two distinguished vertices in S
can be recovered from our encoding.
Lemma 3.5. The length of a shortest path P in Gs from any x P Ss to any y P Cext can be
recovered from the encoding.
Proof. If P contains some vertex of a fundamental cycle separator used in processing s, let v
be the last vertex of P that belongs to the earliest such separator. By choice of the earliest
separator, the x-to-v distance (in Gs ) is stored (S-to-separator distance). By choice of the last
vertex on P that belongs to that separator, the v-to-y distance (in the region of s that contains
P rv, ys) is stored (separator-to-boundary distance). Thus, the length of P can be recovered.
If P contains no such vertex, then x and y are in the same region when the recursion
terminates, so the x-to-y distance (in Gs ) is stored as a S-to-boundary distance.
We extend the previous lemma and show that it applies also to distinguished vertices enclosed
by holes of s (i.e., for S s instead of Ss ).
Lemma 3.6. The length of a shortest path P in Gs from any x P S s to any y P Cext can be
recovered from the encoding.
Proof. The proof is by induction on the nesting depth of slice s. The base case follows from
Lemma 3.5. For the inductive step, if x P Ss we are done by Lemma 3.5, so assume x is enclosed
by some hole h of s.
If P contains some vertex of a fundamental cycle separator used in processing s before hole
h is eliminated, let v be the last vertex of P that belongs to the earliest such separator. By
choice of the earliest separator, the x-to-v distance (in Gs ) is stored (S-to-separator distance),
and by choice of the last vertex of that separator on P , the v-to-y distance (in a region of s
that contains P rv, ys) is stored (separator-to-boundary distance). Thus, the length of P can be
recovered.
If P contains no such vertex, then the artificial vertex vh and y are in the same region R
when either the recursion terminates, or the hole h is eliminated. In either case, the Ch -to-y
distances are stored (hole-to-boundary distance). Decompose P into a maximal prefix P rx, vs
enclosed by the slice s1 whose boundary is Ch , a maximal suffix P rw, ys enclosed by R, and an
infix P rv, ws. The length of the prefix is stored by the inductive hypothesis for s1 . The length of
the infix is represented by the boundary-to-boundary distances for s1 . The length of the suffix
is stored (hole-to-boundary distance).
Finally, we extend the previous lemma and show that it applies to any two distinguished vertices.
Lemma 3.7. The length of a shortest path P in Gs from any x P S s to any y P S s can be
recovered from the encoding.
Proof. Assume, wlog, that both x and y are enclosed in holes of s (the other cases are similar
and less general). If P contains some vertex of a fundamental cycle separator used in processing
s before either hole is eliminated, then let v be a vertex of P that belongs to the earliest such
separator. By choice of the earliest separator, both the x-to-v and the y-to-v distances (in Gs )
are stored (S-to-separator distance). Thus, the length of P can be recovered.
Otherwise, the hole of x and the hole of y are in the same region R when one of them, say the
hole h of x, is eliminated. If P intersects one of the fundamental cycle separators used during
the elimination process of hole h, then let v be the last vertex on the earliest such separator (see
Figure 7). By choice of earliest separator, the x-to-v distance is stored (S-to-separator distance).
By Lemma 3.6, the length of the maximal suffix P rw, ys enclosed in h is also stored. Let u be
the first vertex of P rv, ws that belongs to either Cext or Ch (u exists because y is enclosed by
Ch and v is not).
19

v

q

Cext

t
r

x

y

u

Figure 7: An illustration of one of the cases in the proof of Lemma 3.7. A slice s with two
holes is shown. The boundary Cext is double-lined. A x-to-y shortest path P is shown in solid
black. The vertices x and y belong to different holes of s (black cycles). The path P crosses a
fundamental cycle separator (blue, parts that do not belong to s are dashed) used in eliminating
the hole to which y belongs.
• If u belongs to Cext then the length of P rv, us is stored (separator-to-boundary distance).
In this case, let q be the last vertex of P that belongs to Cext . The length of P ru, qs
is represented by boundary-to-boundary distances for Cext . Let t be the first vertex of
P rq, ys that belongs to Ch . The length of P rq, ts is represented as a hole-to-boundary
distance (when h is eliminated). Let r be the last vertex of P rt, ys that belongs to Ch .
The length of P rt, rs is represented by boundary-to-boundary distances for Ch , and the
length of P rr, ys is represented by Lemma 3.6. See Figure 7 for an illustration.
• If u belongs to Ch then the length of P rv, us is represented as a separator-to-hole distance.
The representation of the suffix P ru, ys is then similar to the previous case.
Finally, we need to treat the case where P does not intersect any fundamental cycle used
in eliminating the hole h. In this case P can be decomposed into a x-to-Cext prefix, a Ch -to-y
suffix, and subpaths of P between vertices of Ch Y Cext . The prefix and suffix are represented by
Lemma 3.6. The other subpaths are represented as hole-to-boundary or boundary-to-boundary
distances as in the two cases above.
?
Finally, we now show that the entire encoding requires only Õp k ¨ nq bits.
The encoding size. The space required for the boundary-to-boundary distances for all slices
is Opn{wq since the total boundary size is Opn{wq, and by Lemma 2.3.
We next bound the total space required for S-to-separator distances for all slices. Whenever
a distinguished vertex stores its distances to a path P explicitly, the total weight of its region
decreases by a constant factor within Õp1q recursive steps (either immediately, if this happens
in the outer recursion, or otherwise by the time the hole-elimination process ends). So this can
happen Õp1q times per distinguished vertex. Because |P | “ Opwq (by the height of Ts ), this
sums up to a total of Õpk ¨ wq bits.
The analysis of the remaining distances is done for each slice separately. We have already
argued that the depth of the recursive process to handle a slice s is Oplog2 nq “ Õp1q. Similarly

20

to the analysis in Section 3.1 of the single hole case, the total space required for storing separatorto-boundary distances using Lemma 2.1 or Lemma 2.4 at all calls at the same recursive level is
Opn{w ` k ` k ¨ wq. For exactly the same reasons, the total space required for storing separatorto-hole distances using Lemma 2.1 at all calls at the same recursive level (this only happens in
the hole-elimination recursion) is Opn{w ` k ` k ¨ wq.
Hole-to-boundary distances are stored using Lemma 2.4 for at most one hole in each region
along the recursion. Each invocation of Lemma 2.4 for hole Ch and boundary fragment bi
requires Õp|Ch | ` |bi |q bits. For a single level of the recursion, this sums up to Õpk ` n{wq
because the total size of all boundaries is Opn{wq and there are Opkq vertices that contribute in
more than one region (endpoints of bi ’s). The bound for S-to-boundary distances is Õpk ` n{wq
for the same reasons.
To conclude,
a size of the entire encoding is bounded by Õpn{w`k¨wq,
? we showed that the total
which is Õp k ¨ nq by choosing w “ n{k.

4

A Tight Lower Bound

Recall that Gavoille et al. [48] show how to construct, given a Boolean k2 ˆ k2 matrix B, a
planar grid GpBq containing Opk 3 q vertices, such that B can be recovered from the distances
between k distinguished vertices of GpBq. This shows that, for k ď n1{3 , encoding all distances
between k vertices of a planar graph requires Θpk 2 q bits. For k ě n1{3 , we consider t Boolean
k
k
2t ˆ 2t matrices B1 , B2 , . . . , Bt . For each of these matrices, we construct a planar grid containing
k 3
k 3
Opp 2t
q q vertices. The disjoint union of all these grids is a planar graph on Optp 2t
q q “ Opk 3 {t2 q
vertices, such that all Boolean matrices can be recovered from the distances between the k
k 2
distinguishedavertices. Hence, encoding all such distances requires Ωptp 2t
q q “ Ωpk 2 {tq bits.
3
Setting t “ k {n we obtain that encoding
? all distances between the k distinguished vertices
of a planar graph on n vertices requires Ωp k ¨ nq bits.

5

Query Time

The goal of Section 3 was to guarantee that all distances between distinguished vertices are
captured, but we were not concerned with the complexity of retrieving such a distance. In
this section we explain how to augment the encoding to allow efficient extraction of the stored
distances.
We start with reformulating our encoding using the notion of dense distance graphs. Vertices
of a dense distance graph are listed explicitly, but its edges are described implicitly with unit
Monge matrices. Each such matrix describes lengths of the edges between every u P U and
v P V , for some subsets of nodes U and V . The matrix is represented using Õp|U | ` |V |q bits as
described in Lemma 2.1. In particular, we may have |U | “ |V | “ 1 and then the matrix simply
stores the length of a single edge explicitly. The size of a dense distance graph is the total
number of vertices plus the sum of |U | ` |V | over all matrices describing length of the edges. By
construction,
our encoding described in Section 3 is based on defining a dense distance graph of
?
size Õp k ¨ nq. Every distinguished node of the original graph is a vertex of the dense distance
graph, and the distance between two distinguished nodes of the original (unweighted) graph is
the same as the distance between their corresponding vertices in the (weighted) dene distance
graph. Fakcharoenphol and Rao designed an efficient algorithm for computing the shortest paths
in such a graph, nicknames the FR-Dijkstra: 3
3

In the original paper and most of the subsequent work, the dense distance graph is obtained from an rdivision of a planar graph. The vertices are the boundary nodes and distances between boundary nodes in the

21

Lemma 5.1 ([45]). Distance between any two vertices of a dense distance graph of size s can
be found in Õpsq time.
?
?
Applying Lemma 5.1 gives us an oracle of size Õp k ¨ nq answering queries in Õp k ¨ nq
time. For very large k, say k “ Ωpnq, the query time is clearly not optimal, as there exists an
?
oracle of size Õpnq answering queries in Õp nq [45] time.
In the remaining part of this section
?
we will describe how to construct an oracle of size Õp k ¨ nq answering queries in Õpn3{4 q time.
To improve the query time, we apply the vanilla planar separator lemma.
Lemma 5.2. For any planar graph G on n nodes, there exists a partition of the nodes of G into
?
sets A, B, and S, such that |A|, |B| ď 32 n, |S| “ Op nq, and there are no edges between the
nodes of A and B.
We recursively apply Lemma 5.2 to construct a hierarchical decomposition of the whole
graph. The recursion is described by a binary tree K, where every node u P K corresponds
to an induced subgraph Gpuq of the original graph. We let npuq and spuq denote the number
of nodesaand distinguished nodes in Gpuq, respectively. We terminate the recursion as soon as
spuq ď npuq. If u P K is a leaf, we define its set of distinguished nodes Dpuq to consists of all
the distinguished nodes of Gpuq. Otherwise, Dpuq consists of the following nodes:
1. the separator of Gpuq,
2. for every child v of u that is a leaf, all the distinguished nodes of Gpvq,
3. for every child v of u that is not a leaf, the separator of Gpvq.
a
Then, we construct a dense distance graph of size Õp npuq|Dpuq|q capturing distances between
any two nodes from Dpuq in Gpuq.
To calculate the distance dG pu, vq between two distinguished nodes u and v in G, we locate
the deepest nodes u1 and v 1 of K, such that u P Gpu1 q and v P Gpv 1 q. Then, we consider the
union of all dense distance graphs constructed for the nodes of K on the paths from u1 and v 1 to
the root. Note that the same node of G might appear in more than one of these dense distance
graphs, and we identify all of its copies. By construction, the obtained dense distance graph
captures the sought distance. Furthermore, its size is bounded by
b
a
a
max Õp npuq|Dpuq|qq “ max Õp npuq npuqq “ Õpn3{4 q.
uPK

uPK

Therefore, by Lemma 5.1 we can answer a query in Õpn3{4 q time. It remains to bound the size
of the resulting oracle.
a
Lemma 5.3. The dense distance graph constructed for node u P K is of size Õp npuq ¨ spuqq.
Proof. To prove thealemma it is enough to bound |Dpuq| by Opspuqq. If u is a leaf, this is clear.
Otherwise, spuq ą npuq and Dpuq consists of the following nodes:
a
1. the separator of Gpuq of size Op npuqq “ Opspuqq.
2. for every child v of u that is a leaf, all spvq ď spuq distinguished nodes of Gpvq,
a
3. foraevery child v of u that is not a leaf, the separator of Gpvq of size Op npvqq “
Op npuqq “ Opspuqq.
same region are represented with multiple Monge matrices. However, it is easy to see that their algorithm work
for any dense distance graph as defined above.

22

Node u has at most two children, so indeed Dpuq “ Opspuqq.
a
ř
To upper bound the size of the oracle, we need to upper bound the sum uPK npuq ¨ spuq.
To this end, we separately consider all nodes u P K such that npuq P rp 23 q``1 n, p 32 q` nq, for every
` “ 0, 1, . . . , Oplog nq. Fix ` and call these nodes u1 , u2 , . . . , ut . Then, no ui is a descendant
of
node of the original graph appears in at most one Gpui q. Therefore,
ř another uj , so every
ř
spu
q
ď
k
and
npu
i
i q ď n. From the latter inequality and the lower bound on npuq we
i
i
3 ``1
obtain that t ď p 2 q . Now we want to upper bound the following sum:
ÿa
npui q ¨ spui q ď
i

dˆ ˙
ÿa
a
2 ` ÿa
n
spui q “ Op n{t ¨
spui qq.
3
i
i

?
From the concavity of f pxq “ x, the above sum is maximized when spui q “ k{t, so we obtain:
ÿa
a
a
?
npui q ¨ spui q “ Op n{t ¨ t ¨ k{tq “ Op k ¨ nq.
i

a
ř
To obtain an upper bound on uPK npuq ¨ spuq, we only need to multiply the above bound by
log n because for every u P K there?exists ` such that npuq belongs to the appropriate interval,
so the total size of the oracle is Õp k ¨ nq.

6

Labeling Schemes for Unit-Monge Matrices

A distance labeling scheme is a way to compress graphs that allows for distributed decoding.
The goal is to assign a label `v for each node v, so that by looking at the labels of two nodes `s , `t
(without access to the original graph) we can infer the distance between them dps, tq. The main
question one asks about such schemes is how small can the labels be? A famous open question is
?
to close the gap between the Op nq upper bound [48, 51] and the Ωpn1{3 q [48] lower bound for
planar graphs. The only known technique capable of proving a tight lower bound is via a lower
bound for the metric compression problem: if you show that the metric cannot be compressed
into Opk ¨ n1{2´ε q bits, then you show that no labels of size Opn1{2´ε q are possible. Our work
deems this approach impassable, since such compressions are indeed possible. Optimistically,
it is natural to ask if our upper bound for compression could lead to a better upper bound for
labeling. Our encoding assigns opn1{2 q bits per node, but can we distribute these bits to the
nodes while allowing any pair of nodes to deduce the distance from their local information? In
this section, we discuss why this seems difficult.
The heart of our encoding is Lemma 2.1, which is repeatedly used to capture pairwise
distances between a large subset of nodes of the graph using space proportional to the size of
the subset. A key part in the proof of the lemma is an efficient encoding of an n ˆ n matrix into
Õpnq bits, as long as it has the unit-Monge property, that is:
M ri ` 1, j ` 1s ` M ri, js ´ M ri, j ` 1s ´ M ri ` 1, js ě 0

for any i, j P r1, n ´ 1s,

|M ri, js ´ M ri ` 1, js| ď 1

for any i P r1, n ´ 1s, j P r1, ns,

|M ri, js ´ M ri, j ` 1s| ď 1

for any i P r1, ns, j P r1, n ´ 1s.

and every M ri, js is an non-negative integer not exceeding n. The corresponding labeling problem
would be to assign a label to every row and every column of M , such that M ri, js can be
computed from the label of the i-th row and the j-th column. We will show that the Õpnq bits
of the encoding cannot be distributed into Õp1q bits per label. In any such labeling scheme,

23

?
some labels must be of length Ωp nq. For completeness, we will also provide a matching upper
?
bound of Õp nq.
We start with recalling the following connection between unit-Monge matrices and permutation matrices. P is a permutation matrix if every row and every column contains at most one
1 and 0s elsewhere. Then, it is straightforward
to verify that, for any permutation matrix P the
ř
1
matrix M defined as M ri, js “ i1 ěi,j 1 ěj P ri , j 1 s is a unit-Monge matrix. In fact, essentially
any unit-Monge matrix can be obtained through such transformation. This is known, see e.g.
Section 2 in [91], but we provide a proof for completeness.
Lemma 6.1. For any unit-Monge matrix M , there exists a permutation matrix P , such that
ÿ
P r2i1 , 2j 1 s.
M ri, js “ Hris ` V rjs `
i1 ěi,j 1 ěj

where H and V are vectors of length n with non-negative entries bounded by n.
Proof. We define an n ˆ n matrix P 1 as follows:
P 1 ri, js “ M ri ` 1, j ` 1s ` M ri, js ´ M ri, j ` 1s ´ M ri ` 1, js.
By Monge, clearly P 1 ri, js ě 0, and by unit P 1 ri, js ď 2. In fact, unit also implies that the
sum in every row and every column of P 1 is at most 2. To see this for rows, consider P 1 ri, 1s `
1 ri, 1s ´ P ri ` 1, 1s ` P ri ` 1, ns ´ P ri, ns,
P 1 ri, 2s ` . . . ` P 1 ri, ns. After telescoping, this is P ř
so by unit at most 2 as claimed. Then, consider i1 ěi,j 1 ěj P 1 ri1 , j 1 s. After substituting the
definition of P 1 and telescoping, this becomes M ri, js ` M rn, ns ´ M ri, ns ´ M rn, js. Hence, if
we define Hris ř
“ M ri, ns ´ M rn, ns{2 and V rjs “ M rn, js ´ M rn, ns{2 it holds that M ri, js “
Hris ` V rjs ` i1 ěi,j 1 ěj P 1 ri1 , j 1 s. Finally, we create an 2n ˆ 2n matrix P , where every 2 ˆ 2
block corresponds to a single P 1 ri, js, that is, the sum of values in the block is equal to P 1 ri, js.
It is always possible to define P so that it is a permutation matrix. To see this, consider a row
of P 1 . The values there sum up to at most 2, say P 1 ri, js “ P 1 ri, j 1 s “ 1 for some j ă j 1 . Then,
P 1 ri, js should correspond to a 1 in the first row of its block and P 1 ri, j 1 s to a 1 in the second row
of its block. If j “ j 1 then in the corresponding block we create two 1s, one per row. Columns
are chosen with a symmetric reasoning.
Due to the above lemma, we can focus on assigning a label to every row ř
and column of P ,
such that given the label of the i-th row and the j-th column we can compute i1 ěi,j 1 ěj P ri1 , j 1 s.
We call this problem labeling n ˆ n unit-Monge matrices for dominance sum queries.
Lemma 6.2. Labeling unit-Monge n ˆ n matrices for dominance sum queries can be done with
?
Op n log nq bits.
Proof. We can assume that there is exactly one 1 in every row and column of P . Therefore,
the input is fully described by a permutation π. Any permutation on n elements can be decom?
?
posed by up to n increasing subsequences I1 , I2 , . . . and up to n decreasing subsequences
D1 , D2 , . . .. The label of every row and every column consists of Oplog nq bits stored for every
?
such subsequence, thus Op n log nq bits in total. We think of every subsequence as a set of
points px1 , y1 q, px2 , y2 q, . . . and the Oplog nq bits corresponding to this subsequence in the label
of the i-th row and the j-th column should be enough to determine the number of points pxk , yk q
such that xk ě i and yk ě j. We separately describe what should be stored for an increasing
subsequence and then for a decreasing subsequence.
Consider an increasing subsequence consisting of points px1 , y1 q, px2 , y2 q, . . ., such that xk ă
xk`1 and yk ă yk`1 for every k “ 1, 2, . . .. Then, the label of the i-th row stores the smallest k
24

such that xk ě i, and similarly the label of the j-th row stores the smallest k such that yk ě j.
By taking the maximum of these two numbers we can determine the number of points pxk , yk q
such that xk ě i and yk ě j.
Now consider a decreasing subsequence consisting of points px1 , y1 q, px2 , y2 q, . . ., such that
xk ă xk`1 and yk ą yk`1 for every k “ 1, 2, . . .. Then, the label of the i-th row stores the
smallest k such that xk ě i. The label of the j-th row stores the largest k such that yk ě j.
Denoting the number stored for the i-th row and the j-th row by ` and r, respectively, the
number of points pxk , yk q such that xk ě i and yk ě j can be calculated as maxp0, r ´ ` ` 1q.
?
Lemma 6.3. Labeling unit-Monge n ˆ n matrices for dominance sum queries requires Θp nq
bits.
?
?
Proof. We conceptually divide an n ˆ n matrix P into blocks of size n ˆ n, thus creating
?
?
an n ˆ n matrix B, where every entry Bri, js corresponds to a block of P . For every block
Bri, js we choose one bit bri, js. We will show that then it is always possible to construct the
?
matrix P , such that all bits bri, js can be retrieved from the labels of rows of the form 1 ` α ¨ n
?
and columns of the form 1 ` α ¨ n. Then it follows that we can encode n bits of information
?
?
in 2 n labels, hence one of these labels must consist of 12 n bits. It remains to construct P .
We construct P incrementally. We call a row or a column of P active if there is no 1 there.
We start with an empty P and keep adding 1s there while making ensure that there is at most
?
one 1 in every row and column. Given the labels of all rows 1 ` α ¨ n and all columns of the
?
form 1 ` α ¨ n we can count 1s in every block of P . The goal is to ensure that this count is
equal to bri, js. Assume that this is already the case for every bri, js such that i ă i1 or i “ i1 and
j ă j 1 and consider bri1 , j 1 s. If bri1 , j 1 s “ 0 we continue. Otherwise, we have to choose exactly one
?
?
active row r in the range r1 ` i1 ¨ n, pi1 ` 1q ¨ ns and exactly one active column c in the range
?
?
r1 ` j 1 ¨ n, pj 1 ` 1q ¨ ns, and set P rr, cs “ 1, thus making both r and c inactive. This clearly
guarantees that there is exactly one 1 in the corresponding block of P . The only problem is to
guarantee that there is at least one active row and column in the appropriate ranges. However,
?
?
we have deactivated less than i1 rows in the range r1 ` i1 ¨ n, pi1 ` 1q ¨ ns so far, and similarly
?
?
less than j 1 columns in the range r1 ` j 1 ¨ n, pj 1 ` 1q ¨ ns, so indeed there is at least one active
row and column that we can use.

References
[1] A. Abboud and G. Bodwin. The 4/3 additive spanner exponent is tight. In 48th STOC,
pages 351–361, 2016.
[2] A. Abboud and G. Bodwin. Error amplification for pairwise spanner lower bounds. In 27th
SODA, pages 841–854, 2016.
[3] A. Abboud, G. Bodwin, and S. Pettie. A hierarchy of lower bounds for sublinear additive
spanners. In 28th SODA, pages 568–576, 2017.
[4] A. Abboud and S. Dahlgaard. Popular conjectures as a barrier for dynamic planar graph
algorithms. In 57th FOCS, pages 477–486, 2016.
[5] A. Abboud, F. Grandoni, and V. V. Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In 26th SODA, pages 1681–1697, 2015.
[6] A. Abboud and V. V. Williams. Popular conjectures imply strong lower bounds for dynamic
problems. In 55th FOCS, pages 434–443, 2014.

25

[7] A. Abboud, V. V. Williams, and H. Yu. Matching triangles and basing hardness on an
extremely popular conjecture. In 47th STOC, pages 41–50, 2015.
[8] I. Abraham, S. Chechik, and C. Gavoille. Fully dynamic approximate distance oracles for
planar graphs via forbidden-set distance labels. In 44th STOC, pages 1199–1218, 2012.
[9] I. Abraham, C. Gavoille, and D. Malkhi. Compact routing for graphs excluding a fixed
minor. In International Symposium on Distributed Computing, pages 442–456. Springer,
2005.
[10] D. Achlioptas. Database-friendly random projections: Johnson-lindenstrauss with binary
coins. Journal of computer and System Sciences, 66(4):671–687, 2003.
[11] A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a
matrix-searching algorithm. Algorithmica, 2:195–208, 1987.
[12] A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of
a matrix-searching algorithm. Algorithmica, 2(1):195–208, 1987.
[13] A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. E. Wilber. Geometric applications
of a matrix-searching algorithm. Algorithmica, 2:195–208, 1987.
[14] A. Aggarwal and J. K. Park. Notes on searching in multidimensional monotone arrays
(preliminary version). In 29th Annual Symposium on Foundations of Computer Science,
White Plains, New York, USA, 24-26 October 1988, pages 497–512, 1988.
[15] A. Aggarwal and S. Suri. Fast algorithms for computing the largest empty rectangle.
In Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo,
Ontario, Canada, June 8-10, 1987, pages 278–290, 1987.
[16] S. Alstrup, S. Dahlgaard, and M. B. T. Knudsen. Optimal induced universal graphs and
adjacency labeling for trees. In 56th FOCS, pages 1311–1326, 2015.
[17] S. Alstrup, I. L. Gørtz, E. B. Halvorsen, and E. Porat. Distance labeling schemes for trees.
In 43rd ICALP, 2016.
[18] S. Alstrup, E. B. Halvorsen, and K. G. Larsen. Near-optimal labeling schemes for nearest
common ancestors. In 25th SODA, pages 972–982, 2014.
[19] S. Alstrup, H. Kaplan, M. Thorup, and U. Zwick. Adjacency labeling schemes and induceduniversal graphs. In 47th STOC, pages 625–634, 2015.
[20] S. Arikati, D. Z. Chen, L. P. Chew, G. Das, M. Smid, and C. D. Zaroliagis. Planar spanners
and approximate shortest path queries among obstacles in the plane. In 4th ESA, pages
514–528. Springer, 1996.
[21] S. Arora, M. Grigni, D. R. Karger, P. N. Klein, and A. Woloszyn. A polynomial-time
approximation scheme for weighted planar graph tsp. In 9th SODA, pages 33–41, 1998.
[22] A. Basu and A. Gupta. Steiner point removal in graph metrics. Unpublished manuscript,
http:// www.math.ucdavis.edu/ ~abasu/ papers/ SPR.pdf , 2008.
[23] G. E. Blelloch and A. Farzan. Succinct representations of separable graphs. In 21st CPM,
pages 138–150, 2010.

26

[24] G. Bodwin. Linear size distance preservers. In 28th SODA, pages 600–615, 2017.
[25] G. Bodwin and V. Vassilevska Williams. Better distance preservers and additive spanners.
In 27th SODA, pages 855–872, 2016.
[26] B. Bollobás, D. Coppersmith, and M. Elkin. Sparse distance preservers and additive spanners. In 14th SODA, pages 414–423, 2003.
[27] G. Borradaile, P. N. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen. Multiple-source
multiple-sink maximum flow in directed planar graphs in near-linear time. In FOCS, pages
170–179, 2011.
[28] G. Borradaile, P. Sankowski, and C. Wulff-Nilsen. Min st-cut oracle for planar graphs with
near-linear preprocessing time. In FOCS, pages 601–610, 2010.
[29] S. Cabello. Many distances in planar graphs. Algorithmica, 62(1-2):361–381, 2012.
[30] S. Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in
planar graphs. In 28th SODA, pages 2143–2152, 2017.
[31] H. T. Chan, D. Xia, G. Konjevod, and A. W. Richa. A tight lower bound for the steiner
point removal problem on trees. In 9th APPROX, pages 70–81, 2006.
[32] S. Chaudhuri and C. D. Zaroliagis. Shortest paths in digraphs of small treewidth. part i:
Sequential algorithms. Algorithmica, 27(3):212–226, 2000.
[33] Y. K. Cheung, G. Goranci, and M. Henzinger. Graph minors for preserving terminal distances approximately - lower and upper bounds. In 43rd ICALP, pages 131:1–131:14, 2016.
[34] Y. Chiang, C. Lin, and H. Lu. Orderly spanning trees with applications to graph encoding
and graph drawing. In 22nd SODA, pages 506–515, 2001.
[35] V. Cohen-Addad, S. Dahlgaard, and C. Wulff-Nilsen. Fast and compact exact distance
oracle for planar graphs. CoRR, abs/1702.03259, 2017.
[36] D. Coppersmith and M. Elkin. Sparse sourcewise and pairwise distance preservers. SIAM
Journal on Discrete Mathematics, pages 463–501, 2006.
[37] M. Crochemore, G. Landau, and M. Ziv-Ukelson. A subquadratic sequence alignment
algorithm for unrestricted scoring matrices. SIAM Journal on Computing, 32:1654–1673,
2003.
[38] M. Cygan, F. Grandoni, and T. Kavitha. On pairwise spanners. In 30th STACS, pages
209–220, 2013.
[39] S. Dahlgaard. On the hardness of partially dynamic graph problems and connections to
diameter. In 43rd ICALP, pages 48:1–48:14, 2016.
[40] D. Delling, A. V. Goldberg, R. Savchenko, and R. F. Werneck. Hub labels: Theory and
practice. In 13th SEA, pages 259–270, 2014.
[41] H. Djidjev. On-line algorithms for shortest path problems on planar digraphs. In 22nd WG,
pages 151–165, 1996.
[42] M. Elkin, Y. Emek, D. A. Spielman, and S.-H. Teng. Lower-stretch spanning trees. SIAM
Journal on Computing, 38(2):608–628, 2008.
27

[43] M. Englert, A. Gupta, R. Krauthgamer, H. Racke, I. Talgam-Cohen, and K. Talwar. Vertex
sparsifiers: New results from old techniques. SIAM Journal on Computing, 43(4):1239–1262,
2014.
[44] D. Eppstein. Dynamic generators of topologically embedded graphs. In 14th SODA, pages
599–608, 2003.
[45] J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, and
near linear time. J. Comput. Syst. Sci., 72(5):868–889, 2006. A preliminary version in 42nd
FOCS, 2001.
[46] C. Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT
News, 32(1):36–52, 2001.
[47] C. Gavoille and D. Peleg. Compact and localized distributed data structures. Distributed
Computing, 16(2-3):111–120, 2003.
[48] C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. Journal of
Algorithms, 53(1):85–112, 2004. A preliminary version in 12th SODA, 2001.
[49] P. Gawrychowski and A. Karczmarz. Improved bounds for shortest paths in dense distance
graphs. CoRR, abs/1602.07013, 2016.
[50] P. Gawrychowski, S. Mozes, and O. Weimann. Submatrix maximum queries in monge
matrices are equivalent to predecessor search. In ICALP, pages 580–592, 2015.
[51] P. Gawrychowski and P. Uznanski. A note on distance labeling in planar graphs. CoRR,
abs/1611.06529, 2016.
[52] G. Goranci, M. Henzinger, and P. Peng. Improved guarantees for vertex sparsification in
planar graphs. CoRR, abs/1702.01136, 2017.
[53] G. Goranci and H. Räcke. Vertex sparsification in trees. In 14th WAOA, pages 103–115,
2016.
[54] R. Graham and H. Pollak. On embedding graphs in squashed cubes. In Graph Theory and
Applications, volume 303 of Lecture Notes in Mathematics, pages 99–110. Springer Berlin
Heidelberg, 1972.
[55] M. Grigni, E. Koutsoupias, and C. Papadimitriou. An approximation scheme for planar
graph tsp. In 36th FOCS, pages 640–645, 1995.
[56] A. Gupta. Steiner points in tree metrics don’t (really) help. In 12th SODA, pages 220–227,
2001.
[57] D. Hermelin, G. Landau, S. Landau, and O. Weimann. A unified algorithm for accelerating
edit-distance via text-compression. Algorithmica, 65:339–353, 2013. Preliminary version in
STACS 2009.
[58] P. Indyk and T. Wagner. Near-optimal (euclidean) metric compression. In 28th SODA,
pages 710–723, 2017.
[59] G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Improved algorithms for
min cut and max flow in undirected planar graphs. In STOC, pages 313–322, 2011.

28

[60] W. B. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space.
Contemporary mathematics, 26(189-206):1, 1984.
[61] L. Kamma, R. Krauthgamer, and H. L. Nguyen. Cutting corners cheaply, or how to remove
steiner points. SIAM Journal of Computing, 44(4):975–995, 2015.
[62] S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. SIAM Journal on
Discrete Mathematics, 5(4):596–603, 1992.
[63] H. Kaplan, S. Mozes, Y. Nussbaum, and M. Sharir. Submatrix maximum queries in Monge
matrices and Monge partial matrices, and their applications. In 23rd SODA, pages 338–355,
2012.
[64] T. Kavitha. New pairwise spanners. In 32nd STACS, pages 513–526, 2015.
[65] T. Kavitha and N. Varma. Small stretch pairwise spanners. In 40th ICALP, pages 601–612,
2013.
[66] K.-i. Kawarabayashi, P. N. Klein, and C. Sommer. Linear-space approximate distance
oracles for planar, bounded-genus and minor-free graphs. In 38th ICALP, pages 135–146,
2011.
[67] M. M. Klawe and D. J. Kleitman. An almost linear time algorithm for generalized matrix
searching. SIAM Journal Discret. Math., 3(1):81–97, 1990.
[68] P. Klein and S. Mozes. Optimization algorithms for planar graphs. http://planarity.org.
Book draft.
[69] P. Klein, S. Mozes, and O. Weimann. Shortest paths in directed planar graphs with negative
lengths: a linear-space Opn lg2 nq-time algorithm. ACM Transactions on Algorithms, 6(2):2–
13, 2010.
[70] P. N. Klein. Multiple-source shortest paths in planar graphs. In 16th SODA, volume 5,
pages 146–155, 2005.
[71] P. N. Klein, S. Mozes, and C. Sommer. Structured recursive separator decompositions for
planar graphs in linear time. In 45th STOC, pages 505–514, 2013.
[72] R. Krauthgamer, H. L. Nguy?n, and T. Zondiner. Preserving terminal distances using
minors. SIAM Journal on Discrete Mathematics, 28(1):127–141, 2014. A preliminary version
in 39th ICALP, 2012.
[73] R. Krauthgamer and I. Rika.
abs/1702.05951, 2017.

Refined vertex sparsifiers of planar graphs.

CoRR,

[74] J. Lacki, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. Single source - all sinks max
flows in planar digraphs. In FOCS, pages 599–608, 2012.
[75] J. Łącki and P. Sankowski. Min-cuts and shortest cycles in planar graphs in Opn log log nq
time. In ESA, pages 155–166, 2011.
[76] S. Mozes and C. Sommer. Exact distance oracles for planar graphs. In 23rd SODA, pages
209–222, 2012.
[77] S. Mozes and C. Wulff-Nilsen. Shortest paths in planar graphs with real lengths in
O(nlog2 n/loglogn) time. In ESA, pages 206–217, 2010.
29

[78] J. I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees
and planar graphs. In 38th FOCS, pages 118–126, 1997.
[79] Y. Nussbaum. Improved distance queries in planar graphs. In Workshop on Algorithms and
Data Structures, pages 642–653. Springer, 2011.
[80] M. Parter. Bypassing erdös’ girth conjecture: Hybrid stretch and sourcewise spanners. In
41st ICALP, pages 608–619, 2014.
[81] D. Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.
[82] D. Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33(3):167–176,
2000.
[83] S. Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1):7:1–7:22, 2009.
[84] L. Roditty and U. Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389–
401, 2011. A preliminary version in 12th ESA, 2004.
[85] B. Saha. Language edit distance and maximum likelihood parsing of stochastic grammars:
Faster algorithms and connection to fundamental graph problems. In 56th FOCS, pages
118–135, 2015.
[86] J. Schmidt. All highest scoring paths in weighted grid graphs and their application to
finding all approximate repeats in strings. SIAM Journal on Computing, 27(4):972–992,
1998.
[87] C. Sommer. Shortest-path queries in static networks. ACM Computing Surveys (CSUR),
46(4):45, 2014.
[88] M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs.
Journal of the ACM, 51(6):993–1024, 2004.
[89] M. Thorup and U. Zwick. Compact routing schemes. In 13th SPAA, pages 1–10, 2001.
[90] M. Thorup and U. Zwick. Approximate distance oracles. Journal of the ACM (JACM),
52(1):1–24, 2005.
[91] A. Tiskin. Semi-local string comparison: algorithmic techniques and applications. CoRR,
abs/0707.3619, 2007.
[92] A. Tiskin. Fast distance multiplication of unit-monge matrices. In SODA, pages 1287–1296,
2010.
[93] G. Turán. On the succinct representation of graphs.
8(3):289–294, 1984.

Discrete Applied Mathematics,

[94] K. G. C. von Staudt. Geometrie der Lage. Bauer und Raspe, Nürnberg, 1847.
[95] V. V. Williams and R. Williams. Subcubic equivalences between path, matrix and triangle
problems. In 51st FOCS, pages 645–654, 2010.
[96] D. P. Woodruff. Lower bounds for additive spanners, emulators, and more. In 47th FOCS,
pages 389–398, 2006.
[97] C. Wulff-Nilsen. Algorithms for planar graphs and graphs in metric spaces. PhD thesis,
PhD thesis, University of Copenhagen, 2010.

30

