Distances and shortest paths on graphs
of bounded highway dimension:
simple, fast, dynamic

arXiv:2312.04235v1 [cs.DS] 7 Dec 2023

Sébastien Collette∗

John Iacono†

Abstract
Dijkstra’s algorithm is the standard method for computing shortest paths on arbitrary
graphs. However, it is slow for large graphs, taking at least linear time. It has been long
known that for real world road networks, creating a hierarchy of well-chosen shortcuts allows
fast distance and path computation, with exact distance queries seemingly being answered in
logarithmic time. However, these methods were but heuristics until the work of Abraham et
al. [JACM 2016], where they defined a graph parameter called highway dimension which is constant for real-world road networks, and showed that in graphs of constant highway dimension,
a shortcut hierarchy exists that guarantees shortest distance computation takes O(log(U + V ))
time and O(V log(U + V )) space, where U is the ratio of the smallest to largest edge, and V
is the number of vertices. The problem is that they were unable to efficiently compute the
hierarchy of shortcuts. Here we present a simple and efficient algorithm to compute the needed
hierarchy of shortcuts in time and space O(V log(U + V )), as well as supporting updates in time
O(log(U + V )).

1

Introduction
Aut viam inveniam aut faciam
—Hannibal

The shortest path and shortest distance problems are fundamental problems in computer science: in the shortest path problem, given an origin and a destination, find the shortest path between
them on the graph. For the shortest distance problem one is interested in the length of the shortest
path and not the path itself.
The classical solution for general graphs G = (V, E) is Dijkstra’s algorithm from the 1950’s [9]
which, when combined with a heap supporting constant time decrease-key operations, such as a
Fibonacci heap [15], can compute shortest paths and distances from any single vertex to all other
vertices in the graph in time O(|V | log |V | + |E|). This algorithm, by computing all paths and
distances from a single vertex, appears to be much too big a hammer when all one is interested in
is the shortest distance between a single pair of vertices, but yet Dijkstra’s is the best known for
general graphs unless one is willing to use superquadratic space and preprocessing by, for example,
computing all-pairs shortest paths (e.g. [24]). Note that here we are only interested in exact
∗

Synapsis Group; work on syty.io supported and subsidized by Innoviris.brussels. sco@synapsis-group.com
Université Libre de Bruxelles & Synapsis Group; work on syty.io supported and subsidized by Innoviris.brussels.
john.iacono@ulb.be
†

1

distances, not approximate ones, which are the subject of the distance oracles literature which
began with [26].
The slowness of Dijkstra’s algorithm is real: to compute a shortest distance on the road map of
the world’s 136th largest country, Belgium, takes half a second on standard hardware. Computing
a single shortest distance query for each Belgian on the map of Belgium would take months of
computation1 , but as the number of Belgians is roughly the same as the graph size, the number of
queries is nowhere near enough to make an all-pairs approach worthwhile, especially if the graph
changes.
However, road graphs are not general graphs, and over time a number of heuristics have emerged
to compute shortest distances and paths radically faster than using Dijkstra on real-world graphs
[2,3,5,6,8,16,17,19,20,23,25] which largely involve in one form or another of adding pre-computed
shortcut edges to the graph. Consider the following method to create a hierarchy of graphs:
• Define a sequence of sets of vertices V = C[0] ⊃ C[1] ⊃ C[2] · · · .
• The number of vertices at level at least i, C[≥ i] should be exponentially decreasing in i:
|C[i]| = Θ( |Vci | ).
• Construct shortcut graphs G[i], which are graphs that can be used to compute shortest paths
among those vertices in C[i]; G[0] = |V |. See Figure 1.
From such a basic structure, which one can think of as a kind of skip list on a graph, one can
search for shortest paths that are bitonic, that is from the origin and destination they start at
level 0, and only consider paths that continue on the same level or continue to a higher level until
the two sides meet in the middle. If such a hierarchy is constructed with nice properties, one can
imagine that logarithmic shortest distance queries are envisionable. Such nice properties would
involve only needing to follow a constant number of vertices at any level before being assured that
one will hit a higher-level vertex, and keeping the degree of the vertices at each level constant.
The first condition is easier than the second to obtain, as a random sample will achieve the first
condition in expectation but utterly fail in maintaining constant degree even when this is possible
though a more considered choice strategy.
How does one compute the shortcut graph G[i] from G[i − 1]? Start with G[i] and incrementally
remove every vertex v in C[i] \ C[i − 1]; when doing so look at all pairs of neighbors v1 , v2 of v; if
the shortest path from v1 to v2 does not go through v do nothing, otherwise add an edge from v1
to v2 weighted with the sum of the edges v1 , v and v, v2 .
Now, the crucial point is that the choice of which vertices should be chosen to be in the next
level can not be made arbitrarily or randomly. There are bad choices. As illustrated in Figure 2,
one choice leads to a quadratic-sized, linear degree, and thus useless, shortcut graph and the other
leads to a nice-looking linear-sized constant-degree graph.
This figure illustrates the main heuristic used in creating these hierarchies: vertices on more
important roads should appear higher up in the hierarchy, and unimportant roads of limited use
such as dead ends should remain in low levels only. How can one determine which roads are
important and which are not? One can get the information from the map metadata or another
source, or attempt to use real-world traffic data to figure it out. However, while this works well,
it remains but a heuristic. Also, deciding on the importance of roads in a fixed manner inhibits
flexibility and the ability to react dynamically, a gravel road may become vitally important if it
can be used to circumnavigate a traffic accident.
1

This is a strong statement to make the reader feel how slow Dijkstra is, we can of course do better with parallel
processing, clustering, etc. But even on a 30-core processor, computing millions of Dijkstra instances will take days.

2

G[3]
2

3

G[2]
1

1

3

3
2
2
3

G[1]
1
2

1

2

1

1

2

1

1

1

G[0]

1
1

1

1

1

1

1

1
1

2

1

1

1

1
1

Figure 1: A shortcut graph hierarchy, where the colored vertices are removed to create the next
level.

3

1
1

1
1

1
1

1
1

1
1

1
1

1
1

1
1

2

2

2

2

4

4

4

4

1

6

6

8

8
6
10

Figure 2: There are bad choices when deciding which vertices should remain in the next shortcut
graph. Given the top graph, the shortcut graph of the green vertices is the middle graph, and the
magenta vertices is the bottom figure. The middle graph is a path and the bottom a clique.

4

In [1], heretoforth referred to as the HD paper, a major break-though was made. They defined a
graph parameter which they called highway dimension, argued that real-world road networks have
small highway dimension, and showed that for graphs of small highway dimension there exists a
hierarchy of C[i]s such that distance queries can be computed in logarithmic time, and shortest path
queries take an additional linear term in the path description complexity. The formal definition
of highway dimension is presented in Definition 2, but informally a graph has constant highway
dimension, if for every v and r, the set of shortest paths of length r that pass close (within 2r) to v
can be covered with a constant number of vertices. Highway dimension has no relation to planarity
other than both have a linear number of edges, and constant highway dimension is stronger than
constant doubling dimension. Highway dimension neither needs an embedding of the graph nor
restricts edge weights to be some distance such as Euclidean.
However, the only problem in the HD paper was they showed only the existence of C[i]s that
work well, given constant highway dimension. No efficient algorithm to compute them was proposed.
We quote from the HD paper, with brackets being our attempt to link their notation to the
discussion so far:
Although Theorem 4.2 guarantees the existence of good hitting sets [the C[i]’s], no
polynomial-time algorithm is known for computing the minimum hitting set H used
in the proof. As a result, no polynomial-time algorithm is known for computing an
optimum multiscale SPHS [hierarchy of C[i]s], which are important building blocks of
the preprocessing phase of the algorithms we analyze in Sections 5 and 6 [shortcut based
algorithms]. Note that in these sections, we analyze the query times assuming optimum
(exponential-time) preprocessing.
Section 8 discusses polynomial-time approximation algorithms for SPHS computation,
which enable polynomial-time preprocessing with a slight degradation of the query
bounds. Although still impractical for large road networks, these polynomial-time preprocessing routines provide some justification for practical variants of preprocessing.
These variants run in polynomial time and produce solutions that have no theoretical
quality guarantee, but work well on real-world problems.
Here we show how to compute C[i]s that are proven to work efficiently for graphs of constant
highway dimension. Our idea, which we motivate further in Section 2, is that a vertex is on
an important road if it is in the middle of a long shortest path. We show that this heuristic
is theoretically sound and algorithmically efficient. As a bonus, we show that we can not only
compute the C[i]s efficiently, we show that we can maintain them under edge insertions, deletions
and re-weightings. We summarize our result with the following theorem:
Theorem 1. Let G be a connected graph with |V | vertices, constant highway dimension, and
ratio of smallest-to-largest edge U . Our data structure supports shortest distance queries in time
O(log(|V |+U )) and shortest path queries whose result is a path with p edges in time O(p+log(|V |+
U )). Our data structure can be computed in O(|V | log U ) time and takes O(|V | log U ) space. The
data structure supports dynamic changes to the graph, edge insertions/deletions/reweighting in time
O(log(|V | + U )).
We note that the space usage is the same as in the HD paper and is linear for unit-edge-weight
graphs. In practice, for open street map data for Belgium, U ≈ 0.6|V |. With some additional
analysis, the space usage of our structure should be able to be shown to be
!
X
weight of largest incident edge to v
O
log
;
weight of smallest incident edge to v
v∈V

5

for the Open Street Map data for Belgium this would be 1.8|V | inside the O() when using the
binary logarithm.
Other work on highway dimension Here we briefly review the literature that uses the notion
of highway dimension. This literature has a similar flavor to treewidth in that a number of problems
have been shown to be more efficiently solvable on graphs of constant highway dimension than on
more general graph classes.
This includes: capacitated vehicle routing [21], generalized k-center [14], the traveling salesperson problem [10], clustering [13], k-center problems [11], and embedding of low highway dimension
graphs into graph of bounded treewidth [12]. In [18], they show that graphs of constant highway
dimension have exponentially smaller 3-hopsets than previously known distance oracles (a k-hopset
is a set of edges added to a graph the does not change shortest path lengths but shortest paths
can be computed only using k edges). In [7] it is shown that finding the smallest set of vertices
that intersect all paths of a certain length in a graph of constant highway dimension is W [1] hard.
In [22], they introduce a new graph parameter, skeleton dimension, and show that hub labeling
schemes in graph with low skeleton dimension are more efficient than for those known for graphs
with small highway dimension.

2

Our approach

Here we describe at a high level our approach. We make one assumption in this section that greatly
simplifies our arguments: all edges in G have unit length, perturbed in such a way that shortest
paths are unique. Much of the complexity in the proofs in the main part of the paper has to do
with making the definitions and proofs work with variable length edges, but our main intellectual
contribution can be presented limiting the discussion to perturbed unit-length edges. We give
forward pointers to the related claims in the main presentation, keeping in mind that the exact
statements often do not match due to the complexities of handling variable-length edges.
We create a hierarchy of graphs called shortcut graphs G[i] (Definition 7) and vertex sets called
vertex covers C[i] (Definition 5) , where C[i] are the vertices of G[i]. The base case has G[0] being
G and C[0] being V . We construct C[i] from G[i − 1] incrementally by initializing C[i] to be empty,
and then looking at all paths in G[i] of length between 34 8i and 8i , and if these paths currently
do not contain a vertex in C[i] add the vertex in G[i] closest to the midpoint of the path to C[i].
The shortcut graph G[i] has edges between vertices of C[i] who do not contain another vertex of
C[i] on their shortest path; these edges are weighted with the shortest-path distance. We call this
the pick-a-vertex-close-to-the-middle-if-there-is-no-vertex-on-the-path-yet method, the full version
is in Definition 22.
This hierarchy has a number of nice properties, assuming constant highway dimension.
• Shortest path lengths between vertices of C[i] in G[i] are the same as in G (Observation 17).
• Vertex degree in all G[i] is constant (Lemma 18).
• Any shortest path of length at least 8i in G contains at least one element of C[i] (Lemma 23).
• Edge length in G[i] is at most 8i (by the previous point, and the meaning of a shortcut graph).
• The size of the part of G[i] graph within distance 8i of any element of C[i] is constant
(Lemma 19).
• The total number of levels is O(log |V |) (Lemma 30).
6

• The total size of all G[i] and C[i] is O(|V |) (Lemma 29).
These properties ensure that the creation of the C[i]’s and G[i] can be done locally by only
examining constant-size pieces of C[i − 1] and G[i − 1] around the parts being created, which
gives linear total construction time (Section 7). It also gives logarithmic update time, since only a
constant sized piece of each G[i] and C[i] needs to be recomputed around any change (Section 8).
Given this structure, a variant of bidirectional Dijkstra can be used to compute the distance
between two vertices using the union of the G[i]s proceeding one level at a time, and it can been
shown that the shortest distance can be found using a path which is bitonic in which level of
G[i] each edge comes from, and only needs to follow a constant number of edges in each G[i].
This ensures that the shortest-path distance can be computed in time O(log d), where d is the
distance. Through appropriate augmentation, the shortest path can by obtained in linear time in
its description by uncompressing the edges in the shortcut graph. Everything described except how
the C[i]s are computed was already shown in the HD paper.
The pick-a-vertex-close-to-the-middle-if-there-is-no-vertex-on-the-path-yet method is the main
new idea, and proving that it works requires one key observation. It was known that if a graph
has constant highway dimension, then for any r there is a set of points C such that every path
of length at least r has an element of C and within distance r of any vertex there are at most a
constant number of elements of C (Lemma 11). We extend this idea to show that there is a set of
paths P of length at least 14 r such that each path p of length at least r contains as a subpath a
path of P that includes the middle of p, and within distance r of any vertex there are at most a
constant number of paths of P (Lemma 20). Intuitively, we show that all long paths not only pass
through a point in a locally sparse point set C, they pass completely through a path in a locally
sparse set of long paths; this makes sense as if one posits long paths all pass through some point on
a highway, they are not on the highway just at one point, but typically for a substantial distance.
We do not compute this path cover P , but use its existence, through a charging argument, to show
that the pick-a-vertex-close-to-the-middle-if-there-is-no-vertex-on-the-path-yet method generates a
valid cover which has the required local sparseness (Lemma 23).
We emphasize that the pick-a-vertex-close-to-the-middle-if-there-is-no-vertex-on-the-path-yet
method is simple and efficient, and the resultant hierarchy of vertex covers which gives efficient
shortest path computation is exactly what was shown to exist in the HD paper but was unable to
be computed.

3

Notation and definitions

In this section we review the definitions surrounding highway dimension, and introduce our concept
of a path cover which is the vital new ingredient which is key to making our algorithm work.

3.1

Notation.

The input graph G is a weighted connected undirected graph. We require that all shortest paths are
unique, and the shortest path between two vertices which are connected by the edge be that edge.
(The latter, which we call the requirement that all edges be useful, is required for Lemma 14 and
is in the HD paper as well). For convenience, we require that all edges have at least unit weight.
We will also assume that the graph G has constant highway dimension, as defined in Definition 4;
many other lemmas make claims about other quantities being constant which are dependent on

7

this assumption2 .
We begin with basic notation:
• UG , the maximum weight edge in G
• pG (v1 , v2 ). The shortest path from v1 to v2 in G, which we have assumed is uniquely determined; Thus if v3 , v4 are on pG (v1 , v2 ), pG (v3 , v4 ) is a subpath of pG (v1 , v2 ).
• dG (vv , v2 ). The distance between vertices is defined as the length of the shortest path, that
is, the sum of the weights of each edge.
• maxedge(p). The maximum weight edge on path p.
• BG (v, r) := {v ′ |dG (v, v ′ ) ≤ r}. The ball of radius r from v, expressed as a set of vertices.
• V (·) the vertices of whatever is in the parenthesis: a graph, a path, a set of edges.
• |e| is the weight of edge e ; we use interchangeably the terms length and weight.
We will occasionally need the continuous view of a weighted graph, where each edge can be
viewed as having an infinity of vertices at each distance along the edge: We will always use a hat
to denote a vertex that conceptually may be on an edge. We use V̂G to denote all possible vertices
including those on edges. A path p̂ in G is the set of all elements of V̂G in the path, and the ball
B̂G (v̂, r) is the union of the paths of length r from v̂ to elements of V̂G in G.
We omit the G subscripts if there is no risk of ambiguity that G is the input graph.

3.2

Several flavors of highway dimension.

Here we present three different variants of the definition of highway dimension. The first, continuous
highway dimension, was central in the conference version of the HD paper, but is dependent on
the continuous view of graphs. The second definition, discrete highway dimension is new here,
and allows simple arguments in many proofs to come. The third, highway dimension without an
adjective, comes from the journal version of highway dimension, and we present it last as it is the
least intuitive.
We show in Section 4.1 that graphs of constant highway dimension have constant continuous
and discrete highway dimension (Corollary 12). Thus, assuming constant highway dimension we
can use whichever of these definitions is the easiest to work with, which is often the discrete highway
dimension.
We begin with the definition central to the conference version of the paper on highway dimension
[4] which is elegant and easy to understand:
Definition 2. Continuous highway dimension, Definition 11.1 of [1] The continuous highway dimension of a weighted graph G = (E, V ) is the minimum h such that for every v̂ ∈ V̂ and
every positive r, there exists a set Ĉ ⊆ V̂ of at most h vertices such that for every v̂1 , v̂2 ∈ V̂ , if
p̂(v̂1 , v̂2 ) ⊆ B̂(v̂, 4r) and d(v̂1 , v̂2 ) > r then p̂(v̂1 , v̂2 ) ∩ Ĉ ̸= ∅.
2

The astute reader will notice that all of our claims of O(1) if highway dimension is constant hide a polynomial
dependence on the highway dimension; thus if highway dimension were to be logarithmic, these constants would
become polylogarithmic in highway dimension. We have chosen to use O(1) in order to reduce the clutter needed to
work out the exact dependence though each lemma and thus improve the readability of the presentation. We also
have made no attempts to minimize this polynomial dependence, always opting for the cleanest argument.

8

Next is our strictly weaker version that we call discrete highway dimension that we will find of
use, it simply repeats the continuous definition but restricts the vertices under consideration to be
vertices of V . In Lemma 10 we show that a graph of continuous highway dimension h has discrete
highway dimension at most h. However, the converse does not hold as, for example, a single vertex
with k incident edges of geometrically increasing weights has constant discrete highway dimension
but Θ(k) continuous highway dimension.
Definition 3. Discrete highway dimension. The discrete highway dimension of a weighted
graph G = (E, V ) is the minimum h such that for every v ∈ V and every positive r, there exists
a set C ⊆ V of at most h vertices such that for every v1 , v2 ∈ V , if V (P (v1 , v2 )) ⊆ B(v, 4r) and
d(v1 , v2 ) > r then V (p(v1 , v2 )) ∩ C ̸= ∅.
Finally we include the definition of highway dimension used in the journal version, [1], which
we wave been referring to as the HD paper. We include this last as in our opinion it is the least
intuitive and requires first introducing and understanding some additional notation. It was shown
in the HD paper with a lemma we restate here as Lemma 11 that continuous highway dimension and
highway dimension are constant-factor equivalent; in this way this definition is a stronger discrete
version of highway dimension than our discrete highway dimension.
Before giving the definition of highway dimension, we introduce the needed notation:
• Given a path p from v1 to v2 , an r-witness of p is a shortest path p′ of length at least r from
v1 or a neighbor of v1 to v2 or a neighbor of v2 that contains p as a subpath.
• A shortest path p is r-significant if it has a r-witness.
• P(r) is the set of all r-significant paths.
• Given a path p and a vertex v the distance d(v, p) is the shortest distance from v to any
vertex of p.
• A path p is (r, d) close to v if it is r-significant, and has a r-witness path p′ such that
d(v, p′ ) ≤ d.
• Let S(v, r) be the set of all paths that are (r, 2r) close to v.
Definition 4. Highway dimension, Definition 3.4 of [1]. The highway dimension of a weighted
graph G = (E, V ) is the smallest h such that for all r > 0 and v ∈ V , there is a set C ⊆ V of at
most h vertices such that for all p ∈ S(v, r), V (p) ∩ C ̸= ∅.

3.3

Definitions

We begin with the notion of a vertex cover, the novel part of our definition compared to previous
work is that paths with long edges are not required to be covered. We will show in Lemma 13 that
graphs of constant highway dimension have vertex covers.
Definition 5. Vertex cover. A (r, k) vertex cover of G = (V, E) is a set of vertices C such that
1. all shortest paths p(v1 , v2 ), v1 , v2 ∈ V , of length d(v1 , v2 ) > r and maxedge(p(v1 , v2 )) ≤ r
have some vc ∈ C where vc ∈ V (p(v1 , v2 )) and
2. for all v ∈ V |B(v, 2r) ∩ C| ≤ k.

9

d(v1 , v2 ) > r
maxedge(p(v1 , v2 )) ≤ r
vc ∈ C

v1 ∈ V

v2 ∈ V

≤ k elements of C
2r
v

Figure 3: Illustration of a vertex cover in red.
Figure 3 illustrates the vertex cover definition.
The notion of a path cover expressed here is novel. We will show in Lemma 20 that graphs of
constant highway dimension have path covers.
Definition 6. Path cover. A (r, η) path cover of G = (V, E), is a set of shortest paths P between
vertices in V , each of length from 14 r to r such that for any v1 , v2 ∈ V where the distance 21 r ≤
d(v1 , v2 ) ≤ r and maxedge(p(v1 , v2 )) ≤ 81 r, p(v1 , v2 ) contains as a subpath some path p(v3 , v4 ) ∈ P ,
where d(v1 , v3 ) and d(v4 , v2 ) are both at most 18 r.
Furthermore, any ball of radius 4r from any v ∈ V contains at least one vertex of at most η
paths in P .
Figure 4 illustrates the definition of a path cover.
Here we present our definition of a shortcut graph. As in the definition of a vertex cover, we
give an upper bound on the length of a path for a shortcut edge to appear, this differs from previous
work.
Definition 7. Shortcut graph, see Section 6.1 of [1]. Given G = (V, E) and C ⊆ V , the
r-shortcut graph of C is G(C, r) = (C, E ′ ) where there is an edge from v1 to v2 in E ′ of weight d
iff d = dG (v1 , v2 ), d ≤ r, and pG (v1 , v2 ) does not contain any elements of C other than v1 and v2 .
The definition of sparse shortest path hitting set (SPHS) is from the HD paper [1]. In spirit the
SPHS, the SPC from the conference version of the HD paper [4], and our vertex covers (Definition 5)
are all the same, but differ in important details. Despite finding the SPHS more cumbersome than
our vertex covers, due to the use of P(r) which has a relatively complex definition, we include
the definition so that we can show how our vertex covers combined with long edges give a SPHS
(Lemma 21), and thus immediately apply those lemmas of [1] that apply to SPHSs to the output
of our algorithm.
Definition 8. Sparse shortest path hitting set (SPHS) An (r, h)-SPHS is a set of vertices
C ⊆ V such that

10

1
2 r ≤ d(v1 , v2 ) < r

(a)

maxedge(p(v1 , v2 )) ≤ 18 r
v1 ∈ V

v4 ∈ V

v3 ∈ V

v2 ∈ V

p(v3 , v4 ) ∈ P

(b)
≤ η paths of P
4r
v

Figure 4: Illustration of a the definition of a path cover. The red paths are the path cover.
1. for all p in P(r), C ∩ V (p) ̸= ∅ and
2. for all v ′ ∈ V , |C ∩ B(v, 2r)| ≤ h.

4

Lemmas about the definitions

In this section we establish a number of facts about the definitions of the previous section, and in
particular for graphs of constant highway dimension.

4.1

Facts about highway dimension

Here we show that graphs of highway dimension have constant degree, and thus |E| = Θ(|V |)
(recall that we only consider connected graphs), and then establish the relationships between the
various variants of highway dimension.
Lemma 9. Degree bound, Lemma 3.5 of [1]. A graph of continuous highway dimension h has
maximum degree h.
Proof. See Figure 5. Consider a vertex v with degree d and shortest incident edge of size 4r. Define
a set of d paths P̂ on each incident edge of v from distance r to distance 3r from v. As these paths
are disjoint, of length greater than r, and inside B(v, 4r), the highway dimension must be at least
h.
Lemma 10. Continuous highway dimension implies discrete highway dimension. A
graph with continuous highway dimension h has discrete highway dimension at most h.
Proof. Fix a v ∈ V and r. See Figure 6. Given a vertex vˆ3 ∈ B̂(v, 4r), define near(v, vˆ3 ) to be the
last vertex in V on the shortest path from v to vˆ3 ; if vˆ3 ∈ V , then near(v, vˆ3 ) = vˆ3 and in general
d(v, near(v3 )) ≤ d(v, v̂3 ).
11

P̂

3r
4r

r
v

Figure 5: Illustration of the proof of Lemma 9.

(a)

v1

vˆ3
near(v1 , vˆ3 )

(b)

4r
v

Figure 6: Illustration of the proof of Lemma 10. In (b), the cyan vertices are the set C and the red
circles indicate elements of Ĉ, which may lie on edges.

12

C 0 := B(v, 2r) ∩ C
C \ C0
C 00

2r
v3

v4

3r

4r

v

v5

Figure 7: Illustration of point (3) in the proof of Lemma 13.
Let
S Ĉ be the set of size at most h that must exist by continuous highway dimension, and let
C := ĉ∈Ĉ near(v, ĉ). Note that since Ĉ ⊆ B̂(v, 4r), C ⊆ B(v, 4r). Also note |C| ≤ |Ĉ| ≤ h.
Consider any v1 , v2 ∈ V such that V (P (v1 , v2 )) ⊆ B(v, 4r). By continuous highway dimension,
there is some ĉ ∈ Ĉ on p̂(v1 , v2 ). Since if ĉ ̸= near(v, ĉ) then near(v, ĉ) is simply one of the two
vertices of the edge ĉ lies on, near(v, ĉ) is also an element of V (p(v1 , v2 )) and C.
Lemma 11. Highway dimension and continuous highway dimension are factor-2 equivalent (Theorem 11.3 of [1]) If G has highway dimension h and continuous highway dimension
h′ , then h ≤ h′ ≤ 2h.
We omit the proof and refer the interested reader to Theorem 11.3 of [1].
Corollary 12. Constant highway dimension implies constant discrete highway dimension and continuous highway dimension. Note that as we have assumed graph G has highway
dimension O(1), by Lemmas 10 and 11 we may assume that G has discrete highway dimension and
continuous highway dimension O(1).

4.2

Facts about a vertex cover

Here we show that graphs of constant highway dimension have a vertex cover. This is similar
in spirit to the proofs found in the HD papers, but the proof is completely different due the the
subtleties of our definition of vertex cover.
Lemma 13. Discrete highway dimension implies vertex cover. Every graph of discrete
highway dimension h has a (r, h) vertex cover for every r.

13

Proof. Let C be a minimum cardinality subset of V that satisfies (1) of the definition of vertex cover (Definition 5): all shortest paths p(v1 , v2 ), v1 , v2 ∈ V , of length d(v1 , v2 ) > r and
maxedge(p(v1 , v2 )) ≤ r have some vc ∈ C where vc ∈ V (p(v1 , v2 )). Such a set always exists as
the set V of all vertices trivially satisfies the covering condition; here we consider the minimal one.
If C satisfies (2) of the definition of (r, h) vertex cover, which requires that for all v ∈ V
|B(v, 2r) ∩ C| ≤ h, then the lemma is proven. We will show that if C does not satisfy (2), then
C is not a minimum cardinality subset of V that satisfies (1) of the definition of vertex cover and
thus will obtain a contradiction.
As (2) of Definition 5 is not satisfied, there must be a vertex v ∈ V such that |B(v, 2r) ∩ C| > h,
let C ′ := B(v, 2r) ∩ C.
Let C ′′ be a set of at most h vertices in B(v, 4r) that intersect all length at least r shortest
paths between vertices in V that lie entirely inside B(v, 4r); this must exist by the definition of
discrete highway dimension (Definition 3).
Observe that since |C ′ | > h and |C ′′ | ≤ h, and thus |C \C ′ ∪C ′′ | < |C|, if we can show C \C ′ ∪C ′′
satisfies (1) of the definition of vertex cover (Definition 5), that would contradict the minimality of
C and prove the lemma.
We will now argue that set C \ C ′ ∪ C ′′ will thus have a nonempty intersection with all shortest
paths p(v1 , v2 ) where d(v1 , v2 ) ≥ r and maxedge(p(v1 , v2 )) ≤ r. This has several cases:
1. First, if V (p(v1 , v2 )) ⊆ B(v, 4r), since d(v1 , v2 ) ≥ r, then C ′′ will intersect V (p(v1 , v2 )), and
thus so will C \ C ′ ∪ C ′′ .
2. Second if V (p(v1 , v2 )) ∩ B(v, 2r) = ∅, then we know there is some element c ∈ C that
intersects V (p(v1 , v2 )) and that c is not an element of C ′ since C ′ ⊆ B(v, 2r); thus c remains
in C \ C ′ ∪ C ′′ .
3. See Figure 7. Thus, thirdly, p(v1 , v2 ) must contain some vertex inside B(v, 2r), call it v3 , and
some vertex outside B(v, 4r), call it v4 . If there are multiple choices for v3 and v4 , choose
them to minimize d(v3 , v4 ); this ensures that V (p(v3 , v4 )) \ {v3 , v4 } contains neither vertices
in B(v, 2r) nor vertices not in B(v, 4r).
Let v5 be the vertex adjacent to v4 on p(v4 , v3 ). Vertex v5 is in the annulus B(v, 4r) \
B(v, 3r); this is because v4 is outside B(v, 4r), and v4 and v5 are connected by an edge with
maxedge(v4 , v5 ) ≤ r.
Note that as v3 is in B(v, 2r) thus d(v3 , v5 ) ≥ r. Also, by construction V (p(v3 , v5 )) ⊆ B(v, 4r).
Thus by the same logic as in the first case, C ′′ will intersect V (p(v3 , v5 )) which is a subset of
V (p(v1 , v2 )), and thus so will C \ C ′ ∪ C ′′ .

4.3

Facts related to doubling dimension

One of the greatest challenges is how to deal with edges of varying lengths, and this lemma shows
that there are not many long edges that intersect any ball.
Lemma 14. Big edges in a ball. In a graph of constant highway dimension, for any r > 0, there
are at most O(1) edges of length at least r with at least one vertex in B(v, 2r).
Proof. Fix v and r and let D denote the set of edges of length at least r with at least one vertex
in B(v, 2r). As we require edges to be useful, each edge of length at least r in D is also a shortest
14

path of length at least r and is in Sr . Thus, by the definition of discrete highway dimension, there
is a set C of size at most h such that each edge in D has as an endpoint at least one vertex in
C. As the maximum degree is h by Lemma 9, each of the at most h elements of C can only be
adjacent to h edges in D; thus |D| ≤ h2 = O(1).
We now show the proof that any graph of constant highway dimension has constant doubling
dimension. However, the converse is easily seen to not be true in the case of a uniform grid; however
large uniform grids are not seen in real word road network, with an emphasis on the word uniform.
Lemma 15. Doubling dimension, Theorem 9.1 of [1]. Given a graph of constant highway
dimension, then any ball B(v, 2r) can be covered with O(1) balls of size r. Precisely, for every v
there exists a set V ′ ⊆ V , |V ′ | = O(1) such that B(v, 2r) ⊆ ∪v′ ∈V ′ B(v ′ , r).
Proof. Let h be the discrete highway dimension of G, this is O(1) by Corollary 12. Let C be vertices
in a (r, h) vertex cover of G that intersect B(v, 2r), such a vertex cover exists by Lemma 13. Let D
be the vertices of edges entirely in B(v, 2r) that have length at least r, there are at most O(1) such
edges Lemma 14. We argue that the balls of size r centered at the elements of V ′ := D ∪ C ∪ {v}
cover B(v, 2r). As B(v, r) is covered from v, we need only worry about B(v, 2r) \ B(v, r). Consider
some v ′ in B(v, 2r) \ B(v, r). The path p(v ′ , v) is in the ball B(v, 2r) and has length at least r. In
the first r of p(v ′ , v) there is either an edge of length > r, in which case there is a vertex of D, or
not, in which case since the maximum edge is less than r there must be an element of c ∈ C of C
in the first r of p(v ′ , v). In either case v ′ ∈ B(v, r).
We can recurse on this lemma so that it can be applied to ball size ratios other than two:
Corollary 16. Generalized doubling. In a graph with constant highway dimension, for any
r
′
′
v ∈ V and
S r ≥ r >′ 0 such that r′ = O(1), there is a set V ⊆ V of size O(1) such that
B(v, r) ⊆ v′ ∈V ′ B(a, v ).

4.4

Facts about shortcut graphs

The shortcut graph has been constructed so that in can be used instead of the original graph
between edges of C that are at most distance r apart.
Observation 17. Let C be a subset of V . For any v1 , v2 ∈ C, and positive r, if maxedge(p(v1 , v2 )) ≤
r:
• dG (v1 , v2 ) = dG(C,r) (v1 , v2 )
• If vertex v3 ∈ C is on pG(C,r) (v1 , v2 ), then v3 is also on pG (v1 , v2 )
Now, we show that vertices of shortcut graphs of vertex covers have small degree:
Lemma 18. Degree of shortcut graph, similar to Lemma 4.2 of [4]. Given a (r, k) vertex
′
cover C of G, and a positive r′ such that rr = O(1), the shortcut graph G(C, r′ ) has maximum
degree O(1).
Proof. In G(C, r′ ), each vertex v ∈ C is only connected to vertices v ′ ∈ C which are in B(v, r′ ). By
the definition of vertex cover and Corollary 16 there are only O(1) such vertices.
Additionally, we show that the complexity of all items in a ball is small; this is important as
our data structures in next section will have a size proportional to degrees and vertices of shortcut
graphs :
15

1
r ≤ d(v1 , v2 ) ≤ r
2

≤ 18 r

v1 ∈ V

maxedge ≤ 18 r

1
r ≤ d(v3 , v4 ) ≤ r
4

v3 ∈ C

≤ 18 r

v4 ∈ C

v2 ∈ V

p(v3 , v4 ) ∈ P

Figure 8: Illustration of point (2) of Lemma 20.
Lemma 19. Shortcut size. Given a (r, k) vertex cover C of G and a positive r′ such that
r′
′
′
r = O(1), for any v the complexity (the sum of vertex degrees) of B(v, r ) ∩ C in G(C, r ) is O(1).
Proof. As noted in the proof of Lemma 18, there are only O(1) vertices in B(v, r′ ) ∩ C, and by
Lemma 18 they have degree O(1).

4.5

Facts about a path cover

Path covers are a completely new idea of this work.
Lemma 20. Highway dimension implies path cover. A graph with constant highway dimension has a (r, O(1)) path cover for any r > 0 (the constant in the O(1) depends on the highway
dimension but it is independent of r).
Proof. Let h be the discrete highway dimension of G; h = O(1) by Corollary 12. Let C be a ( 18 r, h)
vertex cover, which exists by Lemma 13. Let P be the set of the shortest paths between elements
of C that are of length between 41 r and r. Formally:


1
P := p(x1 , x2 ) v1 , v2 ∈ C and r ≤ d(v1 , v2 ) ≤ r
4
We argue that P is a r, O(1) path cover. This requires arguing each requirement to be a path
cover holds:
1. P is a set of shortest paths between vertices in V , each of length from 14 r to r.
This is by construction.
2. For any v1 , v2 ∈ V where the distance 21 r ≤ d(v1 , v2 ) ≤ r and maxedge(p(v1 , v2 )) ≤ 81 r,
p(v1 , v2 ) contains as a subpath some path p(v3 , v4 ) ∈ P , where d(v1 , v3 ) ≤ 81 r and d(v4 , v2 ) ≤
1
8 r.
See Figure 8. Let p be some path p(v1 , v2 ) where the distance 21 r ≤ d(v1 , v2 ) ≤ r and
maxedge(p(v1 , v2 )) ≤ 18 r. Let v3 be a vertex of C on p such that d(v1 , v3 ) ∈ [0, 81 r] and let v4
be a vertex of C on p such that d(v4 , v2 ) ∈ [0, 81 r].
These exist by the definition of a vertex cover, are distinct, and meet the distance requirements. By construction, the distance between v3 and v4 is between 41 r and r and thus p(v3 , v4 )
is an element of P .
16

3. Any ball of radius 4r contains at least one vertex of a constant number paths in P .
By Corollary 16, each ball B(v, 4r) can be covered by O(1) balls of radius 18 r. Each of these
balls intersects at most h elements of C, which bounds |B(v, 5r) ∩ C| by O(1). A path in P
with any vertex in B(v, 4r) must have both endpoints in B(v, 5r), and thus there are at most
|B(v, 5r) ∩ C|2 = O(1) such paths.

4.6

Facts about a SPHS

Here we link our vertex covers and show that together with long edges one obtains a SPHS of [1].
Lemma 21. A vertex cover and long edges give a SPHS Let E ′ be the set of edges in G of
length at least r/3. Let C be a (r/3, k) vertex cover. Then C ∪ V (E ′ ) is a (r, O(1))-SPHS, given G
has constant highway dimension.
Proof. We argue each requirement of a SPHS separately:
1. For all p in P(r), C ∩ V (p) ̸= ∅.
Consider some path p in Pr and let p′ be its r-witness. If maxedge(p′ ) ≥ 3r , then p will contain
a vertex of E ′ . Otherwise, we know that the length of p′ is at least r, and the up to two edges
in p′ but not in p are at most 3r , thus p is has length least 3r ; since maxedge(p′ ) ≤ 3r , there
must be an element of C on p.
2. For all v ′ ∈ V , |C ∩ B(v, 2r)| = O(1).
The number of elements in |B(v, r/3) ∩ C| is at most k by Definition 5. By Corollary 16,
there are at most O(1) elements in |B(v, r) ∩ C|.
The number of elements in |E ′ ∩B(v, 2r)| has at most h2 edges inside by Lemma 14. Applying
Corollary 16, |E ′ ∩ B(v, 4r)| is at most O(1).

5

Creating a SPHS hierarchy

In this section we describe how to create a SPHS hierarchy, which will use a hierarchy of vertex
covers, endpoints of long edges, and their associated shortcut graphs. We focus on a combinatorial
description here, and will address algorithmic issues in Section 7.

5.1

Definitions

We describe the edge sets E[i], the graphs G[i], and the vertex sets C[i] and C ′ [i], where i an integer
at least −1.
E[i] is the set of all edges of length in (8i−1 , 8i ]; recall that all edges have
S∞at least unit length,
thus the E[i] partition the edges and E[−1] = ∅. We use E[≥ i] to denote j=i E[j].
The graph G[−1] is empty as is the vertex set C ′ [−1]. The set C[i] is defined to be C[i] :=
′
C [i] ∪ V (E[≥ i]), with the goal that C[i] is a (8i , O(1)) vertex cover assuming constant highway
dimension h, which we will prove in Lemma 23. G[i] is the shortcut graph G(C[i], 8i ).
The set C ′ [i] is defined based on C[i − 1]; note as there is some flexibility as to what can be in
C ′ [i] we speak of a valid C ′ [i] as one that meets the requirements below:
17

Definition 22. C ′ [−1] := ∅. For integer i ≥ 0 a valid C ′ [i] is any subset of C[i − 1] that can be
produced by the following method:
• Initialize C ′ [i] to be ∅
• For each v, v ′ ∈ V (G[i − 1]) such that dG[i−1] (v, v ′ ) ∈ [ 34 · 8i , 8i ] and maxedgeG (p(v, v ′ )) ≤
8i−1 , if the path pG[i−1] (v, v ′ ) does not yet contain any element of C ′ [i], add the vertex of
G[i − 1] closest to the midpoint of pG[i−1] (v, v ′ ) to C ′ [i]. This can be done using G[i − 1] by
Observation 17.
Note that the order in which all possible (v, v ′ ) pairs are considered is arbitrary, and in general
different orderings will yield different C ′ [i]’s, all of which are valid.

5.2

The C[i]’s are vertex covers

Lemma 23. C[i] is a vertex cover. Each C[i] is a (8i , O(1)) vertex cover of G.
Proof. We proceed by induction on i. First, the base case of C[−1], where we argue each requirement of a vertex cover separately:
1. All shortest paths p(v1 , v2 ), v1 , v2 ∈ V , of length d(v1 , v2 ) > 8−1 and maxedge(p(v1 , v2 )) ≤ 8−1
have some vc ∈ C where vc ∈ V (p(v1 , v2 )).
This holds trivially as we assume all edges have at least unit length.
2. For all v ∈ V |B(v, 2) ∩ C[−1]| = O(1).
As C ′ [−1] is defined to be ∅ and E[−1] is also ∅ due to the minimum unit edge length
requirement, this holds trivially as C[−1] = C ′ [−1] ∪ E[−1] = ∅.
We now prove C[i] is a (8i , O(1)) vertex cover of G, given C[i − 1] is a (8i−1 , O(1)) vertex cover
of G (we note the O(1) is the same for all values of i and depends only on the highway dimension).
We argue each requirement of a path cover separately.
1. All shortest paths p(v1 , v2 ), v1 , v2 ∈ V , of length d(v1 , v2 ) > 8i and maxedge(p(v1 , v2 )) ≤ 8i
have some vc ∈ C where vc ∈ V (p(v1 , v2 )).
Fix some path p(v1 , v2 ) of length d(v1 , v2 ) > 8i where maxedge(p(v1 , v2 )) ≤ 8i .
There are two cases, depending on the relationship of maxedge(p(v1 , v2 )) with 8i−1 . If
maxedge(p(v1 , v2 )) > 8i−1 , then 8i−1 < maxedge(p(v1 , v2 )) ≤ 8i . Thus there is some edge in
E[i] on p(v1 , v2 ), and since C[i] := C ′ [i] ∪ V (E[i]) this completes the proof of this case.
Otherwise, maxedge(pG (v1 , v2 )) ≤ 8i−1 . See Figure 9. Thus, as C[i − 1] is an (8i−1 , O(1))
vertex cover, there must be vertices v6 , v7 ∈ C[i − 1] on pG (v1 , v2 ) such that dG (v1 , v6 ) ≤ 8i−1
and dG (v1 , v7 ) ∈ [7 · 8i−1 , 8 · 8i−1 ]. This implies that dG (v6 , v7 ) ∈ [ 34 8i , 8i ]; thus the path
pG[i−1] (v6 , v7 ) will be considered by the algorithm that constructs C ′ [i] and a vertex on the
path will be added if it was not there already.
2. For all v ∈ V |B(v, 2 · 8i ) ∩ C[i]| = O(1).
We first bound |B(v, 2 · 8i ) ∩ C ′ [i]|.
Let P be a (8i , O(1)) path cover of G, which exists by Lemma 20. Consider a function ρ that
maps every path p(v1 , v2 ), d(v1 , v2 ) ∈ [ 34 8i , 8i ] to some p(v3 , v4 ) ∈ P , v3 , v4 ∈ V , that is a

18

maxedge ≤ 8i−1

d(v1 , v2 ) > 8i

≤ 8i−1

d(v6 , v7 ) ∈ [ 34 8i , 8i ]

v1 ∈ V

v2 ∈ V
v6 ∈ C[i − 1]

v7 ∈ C[i − 1]

Figure 9: Case where maxedge(pG (v1 , v2 )) ≤ 8i−1 in (1) of Lemma 23.
.

maxedge ≤ 8i−1

3 i
8 ≤ d(v5 , v6 ) ≤ 8i
4

1 i
8 ≤ d(v9 , v10 ) ≤ 8i
4

≤ 8i−1

v5

∈
C[i − 1]

≤ 8i−1

v7

≤ 8i−1

v9

v10

v8
∈
V

∈
C[i − 1]

∈
C[i − 1]

∈
V

≤ 8i−1

v6

∈
C[i − 1]

≥ 38 8i

≥ 38 8i
Midpoint of v5 , v6

p(v7 , v8 ) = ρ(p(v5 , v6 ))

Figure 10: Illustration of when the algorithm for constructing C ′ [i] adds an element c to C ′ [i] inside
B(v, 2 · 8i ) after looking at some v5 , v6 ∈ C[i − 1] and finding no elements of C ′ [i] on p(v5 , v6 ) in
(2) of the proof of Lemma 23.

19

subpath of p(v1 , v2 ) and where d(v1 , v3 ) ≤ 81 8i and d(v4 , v2 ) ≤ 81 8i ; this exists by Lemma 20
and Definition 6.
Consider when the algorithm for constructing C ′ [i] adds an element c to C ′ [i] inside B(v, 2·8i )
after looking at some v5 , v6 ∈ C[i − 1] and finding no elements of C ′ [i] on p(v5 , v6 ). See
Figure 10. Recall the algorithm only considers p(v5 , v6 ) if maxedge(v5 , v6 ) ≤ 8i−1 . We know
d(v5 , v6 ) ∈ [ 43 8i , 8i ] by the definition of the algorithm. Thus path ρ(p(v5 , v6 )) is well defined,
which we will denote as p(v7 , v8 ), and d(v5 , v7 ) ≤ 81 8i and d(v6 , v8 ) ≤ 81 8i . Let v9 and v10
be vertices of C[i − 1] on p(v7 , v8 ) such that d(v7 , v9 ) ≤ 18 8i and d(v8 , v10 ) ≤ 18 8i ; these exist
as by assumption C[i − 1] is an (8i−1 , O(1)) vertex cover. Thus since d(v5 , v9 ) ≤ 41 8i , and
d(v5 , v6 ) ∈ [ 43 8i , 8i ], the vertex v9 is on the first half of p(v5 , v6 ); symmetrically, v10 is on the
second half of p(v5 , v6 ). The algorithm will choose c such that it is the element of C[i − 1]
on p(v5 , v6 ) closest to the midpoint of p(v5 , v6 ), since v9 and v10 are elements of C[i − 1] and
are on p(v7 , v8 ) which is a subpath of p(v5 , v6 ), we know c is on p(v7 , v8 ) = ρ(p(v5 , v6 )) and
ρ(p(v5 , v6 )) previously had no elements of C ′ [i]. Furthermore ρ(p(v5 , v6 )) is inside B(v, 3 · 8i )
as c is inside B(v, 2 · 8i ) and c is on ρ(p(v5 , v6 )) which has maximum length 8i .
Thus the size of C ′ [i]∩B(v, 2·8i ) is at most the number of paths in P that intersect B(v, 3·8i ).
As P is a (8i , O(1)) path cover, we know that there are at most O(1) paths in P that intersect
any ball B(v, 4 · 8i ).
We have thus bounded the size of C ′ [i]∩B(v, 2·8i ) to be O(1), and Lemma 14 and Corollary 16
bound the size of E[i] ∩ B(v, 2 · 8i ) to be O(1).
Recalling that C[i] = C ′ [i] ∪ E[i] completes the lemma.

5.3

The C[i]’s are SPHS’s

Lemma 24. The C[i]’s are SPHS’s.
Proof. We know that C[i] is a (8i , O(1)) vertex cover. We also know that C[i] contains the endpoints
of all edges of length at least 8i−1 . Thus by Lemma 21, C[i] is a (3 · 8i , O(1))-SPHS.

6

Bounding the size and height of the structure

Given C ⊆ V and r > 0, let BallCoverG (C, r) be a minimum cardinality subset C ′ of C such that
[
C⊆
BG (v, r).
v∈C ′

Let BC[i] := BallCover(C[i], 8i ), and let IG[i] be the graph with BC[i] as vertices and edges
between elements of BC[i] if their distance is at most 3 · 8i :
IG[i] := (BC[i], {{v1 , v2 }|v1 , v2 ∈ BC[i] and d(v1 , v2 ) ≤ 3 · 8i ).
Lemma 25. High levels of IG[i] are connected. For all i such that log8 U < i the graph IG[i]
is connected.
Proof. Fix i. Let the witness ball of v, β(v), be some element v ′ of BC[i] such that v ∈ B(v ′ , 8i ), with
the specific condition that if v ∈ BC[i], β(v) = v. Consider any two v1 , v2 that are adjacent in G.
20

We argue that β(v1 ) and β(v2 ) are adjacent in IG[i]. Note that d(β(v1 ), v1 ) and d(β(v2 ), v2 ) are both
at most 8i by construction. We also know that d(v1 , v2 ) ≤ U ≤ 8k , and thus d(β(v1 ), β(v2 )) ≤ 3 · 8i ,
which means that β(v1 ) and β(v2 ) are connected in IG[i].
This shows that any v3 , v4 ∈ BC[i] are connected in IG[i] as for each adjacent v1 , v2 on p(v3 , v4 ),
their witness balls β(v1 ) and β(v2 ) are connected in IG[i] and β(v3 ) = v3 and β(v4 ) = v4 .
Lemma 26. Maximum degree of intersection graph. The maximum degree of IG[i] is O(1).
Proof. If v1 , v2 is an edge in IG[i], thus v1 , v2 ∈ C[i] and d(v1 , v2 ) ≤ 3 · 8i . By Corollary 16,
and Lemma 23 which shows that C[i] is a (8i , O(1)) vertex cover, there are only O(1) elements of
C[i] ∩ B(v1 , 3 · 8i ).
Lemma 27. Relating covers of different size balls. There S
is a positive constant cvc < 1 such
that for all i > log8 U , there is a set V C[i] such that C[i] ⊆ v∈V C[i] B(v, 8i+1 ) and |V C[i]| ≤
cvc |BC[i]|. That is, BallCover(C[i], 8i+1 ) ≤ cvc · |BallCover(C[i], 8i )|.
Proof. Turan’s theorem states that any graph G of average degree dG has an independent set of
dG
1
size at least 1+d
|V | and a vertex cover of size at most 1+d
|V |. Thus, as IG[i] has average degree
G
G
at most O(1), IG[i] has a vertex cover of size at most cvc |BC[i]| for some positive cvc < 1. Call
such a cover V C[i].
S
Observe that C[i] ⊆ v∈V C[i] B(v, 3 · 8i ) since every element of C[i] is either in B(v, 8i ) for some
v ∈ V C[i] or in some B(v ′ , 8i ) that intersects B(v, 8i ). This requires that V C[i] is connected as
proved in Lemma 25, as a vertex cover simply ensures that there is one vertex in the cover adjacent
to every edge and does not require that degree-0 vertices be in the cover.
Lemma 28. Ball cover sizes are geometric. When i ≥ log8 U + 1, |BC[i]| ≤ cvc · BC[i − 1]
Proof. We use the fact that by construction C[i] ⊆ C[i − 1]:
|BC[i]| = |BallCover(C[i], 8i )|

Definition
i

≤ BallCover(C[i − 1], 8 )

C[i] ⊆ C[i − 1]
i−1

≤ cvc BallCover(C[i − 1], 8

)

Lemma 27

Lemma 29. Size of the structure The sum of the sizes of the nonempty elements of C[i], C ′ [i],
E[i], and G[i] are all O (|V | log U ) for constant h.
Proof. It suffices to bound C[i] as C ′ [i] is a subset of C[i], and G[i] has elements of C[i] as vertices
and its vertices have degree at most O(1) by Lemma 18. The E[i] partition the edges, and |E| is
at most O(|V |) by Lemma 9.
P
Let k = ⌈log8 U ⌉ + 1. Every C[i] has size at most |V |, thus k−1
i=0 |C[i]| = O(|V | log U ).
We know |BC[k]| ≤ |V | and when
P i > k, there is a positive cvc < 1 such that |BC[i]| ≤
cvc · |BC[i − 1]| by Lemma 28. Thus ∞
i=k |BC[i − 1]| = O(|V |). Additionally, |BC[i]| = Θ(C[i]),
since each ball
P in BC[i] must intersect at least 1 and at most a constant number of elements of
C[i]. Thus ∞
i=k C[i] = O(|V |).
Lemma 30. Height of the structure. The maximum nonempty C[i] is h = O(log(|V | + U )).
Proof. Let k = ⌈log8 U ⌉ + 1. We know |BC[k]| ≤ |V | and when i > k, |BC[i]| ≤ cvc · |BC[i − 1]| for
some positive cvc < 1 by Lemma 28. Thus |BC[k + m]| will reach zero for some m = O(log |V |),
and when |BC[k + m]| = 0, C[i] is empty.
21

7

Computing the structure

The structure is designed to be computed in time linear in its size.
The set C ′ [i] can be computed from C[i − 1] by looking from every v ′ ∈ C[i] at those vertices
in G[i] that are at most 8i from v. By Lemma 23, C[i − 1] is a (8i−1 , O(1)) vertex cover, and since
G[i − 1] has maximum degree O(1) by Lemma 19, it only takes constant time to examine all O(1)
vertices in G[i − 1] that are at most 8i from v.
Note that when looking at an edge v1 , v2 in a shortcut graph, we need to know the value
of maxedge(p(v1 , v2 )) in G; this information can easily be augmented on each shortcut edge and
computed in constant time at the time of its construction.

8

Computing shortest paths and supporting dynamic changes

One familiar with the work done in [1] will realize that, as in previous sections we described how
to compute efficiently a hierarchy of SPHS’s, we can directly apply the result of [1] and conclude
that it is possible to construct a data-structure supporting shortest distance, shortest path queries
and others.
However, one main achievement of this work is to be able to update our structure to allow
queries on dynamically changing graphs. The queries we support are where vertices and edges
can be added, deleted, or re-weighted. The issue with the proposed approach in [1] is that once
the SPHS’s are defined, these are used as input to construct a new data-structure globally. We
would want to find a strategy where local changes are only perturbing the data structure locally.
Therefore we will start by showing how to maintain the C[i]’s, and how to execute queries directly
on the G[i]’s.

8.1

Maintaining C[i]’s

We assume that we have a graph G = (V, E) for which we already computed our structure, that is
we already have a set of C[i], C ′ [i], E[i] and G[i] for all i. Suppose we have an update (insertion,
deletion and weight change); we always consider updates to be edge-related, and because we work
on connected graphs, removing the last edge adjacent to a vertex implies the deletion of the vertex;
while if an edge is added it must always have one of its endpoints already present in G.
We denote the updated edge by e = (v1 , v2 ) and by G∗ = (V ∗ , E ∗ ) the final graph after the
update.
Remember that our algorithm to construct C[i] proceeded, for each i, by considering all pairs of
vertices from G[i−1] whose shortest path in G has length in [ 34 ·8i , 8i ] and maxedgeG (p(v, v ′ )) ≤ 8i−1 .
We will assign pairs of vertices to a color to distinguish them, by extension we say that we color
shortest paths, while we actually mean assign a color to its defining pair of vertices.
We color this collection of shortest paths as follows (See Figure 11):
• In red all the shortest paths that resulted in adding a vertex to C ′ [i], and which contain at
least one vertex outside of B(v1 , 2 · 8i ) ∩ B(v2 , 2 · 8i ).
• In black all the shortest paths that did not result in adding a vertex to C ′ [i], and which
contain at least one vertex outside of B(v1 , 2 · 8i ) ∩ B(v2 , 2 · 8i ).
• In blue all the remaining shortest paths of the collection.
This coloring scheme depends on the updated edge and the actual order used by the algorithm.
By extension, we say that a vertex of a C ′ [i] is red or blue if it has been added by a corresponding
22

2 · 8i

v1

2 · 8i

v2

Figure 11: Illustration of coloring of the paths and vertices in Section 8.1.
shortest path. In case where either v1 or v2 was not in G, we only consider the ball centered at the
endpoint that exists in both graphs; and all balls are BG , i.e. defined based on the weight in G.
To process the update of edge e, we do as follows: we start from C ′ [i], we remove all the
blue vertices to obtain the set Cinit , then we apply our incremental algorithm from Definition 22
initializing C ′∗ [i] to Cinit , to obtain C ′∗ [i] on all the shortest paths of G∗ that do contain a vertex
of B(v1 , 2 · 8i ) and B(v2 , 2 · 8i ). C ∗ [i] is then computed by (a) performing the same changes as in
C ′∗ [i] and (b) correcting the edges E[> i] if the updated edge e has changed weight, was added or
removed.
Our claim is as follows: we will show that if we construct C ∗ [i]’s and C ′∗ [i]’s directly using
Definition 22 on G∗ , there exists an ordering of the pairs of vertices from G∗ [i − 1] that will result
in the exact same sets as the ones obtained by the update. This proves that our updating scheme
results in valid C[i]’s. The proof is inductive and it trivially holds for i = −1.
Lemma 31. All shortest paths with length smaller than 8i and maxedgeG (p(v, v ′ )) ≤ 8i−1 of G[i−1]
that contain at least one vertex outside of B(v1 , 2 · 8i ) ∪ B(v2 , 2 · 8i ) are also shortest paths in G∗ [i].
Proof. Let s be one of these shortest paths. Because s has length smaller than 8i and contains a
vertex outside of B(v1 , 2 · 8i ) ∪ B(v2 , 2 · 8i ), we know that every vertex of s is at distance at least
8i from v1 and v2 or that dG∗ (v1 , v2 ) > 8i . So s does not contain the edge e and no path including
e from v1 to v2 has length smaller than 8i .
In particular, this implies that black and red sets of shortest paths from the construction of
C[i] will be considered when building C ∗ [i]. We will see below that reds will stay red (i.e. will still
need to be covered by a vertex in C ∗ [i]), but that some black could need to be covered in C ∗ [i]
while they did not generate a vertex in C[i].
A shortest path with length in range [ 34 · 8i , 8i ] and maxedgeG (p(v, v ′ )) ≤ 8i−1 is called a
considered shortest path.

23

Lemma 32. All considered shortest paths of G∗ [i − 1] that do not contain a vertex of B(v1 , 2 · 8i ) ∪
B(v2 , 2 · 8i ) are properly covered by Cinit .
Proof. This is by construction: by Lemma 31, the set of considered shortest path outside of the
balls exists in both graphs, so if Cinit covers those paths in C ′ [i], it also covers them in C ′∗ [i]. Note
that all these shortest paths are red or black paths, and Cinit contains all red vertices of C ′ [i]. So
we already know that all red paths strictly outside of the balls are covered. It remains to see that
black shortest path strictly outside of the balls could not be covered by a blue vertex, as no blue
vertex is outside of the balls by definition of blue.
Lemma 33. There exists an ordering of the red shortest paths such that the set Cinit corresponds to
the intermediate C ′∗ [i] obtained by the method of Definition 22 after we only considered red shortest
paths.
Proof. If we apply the algorithm by considering red shortest paths in the same order as in the
original C[i], we know that each red path will require to add a new vertex to C ′∗ [i], and Cinit is
exactly the set of all those red vertices.
Lemma 34. Applying the algorithm of Definition 22, starting with the set Cinit and applying the
process to all considered shortest paths that have at least one vertex inside B(v1 , 2 · 8i ) ∪ B(v2 , 2 · 8i )
results in a valid C ∗ [i].
Proof. It suffices to notice that the proposed algorithm is equivalent to starting with an empty
C ′∗ [i], then starting with all red shortest paths (whose corresponding vertices are those in Cinit ),
then with all black shortest paths, and then the remaining ones. Note that pairs that did not exist
in the original graph will need to be considered if v1 or v2 is a new vertex or if the weight change
results in new candidates inside the ball.
Notice that processing considered shortest paths outside of the balls is not necessary, as we
already know that they are covered in Cinit , and that all path that will add something to Cinit are
path with at least one vertex inside the ball; which is exactly the set of path we consider.
The astute reader will note that by visiting all considered shortest paths including a vertex of
one of the balls, we will re-visit paths that are already covered in Cinit , and that some path that
were previously black could now generate a vertex.
Lemma 35. For each i, updating G[i], C[i], C ′ [i], E[i] to get G∗ [i], C ∗ [i], C ′∗ [i], E ∗ [i] after
insertion, deletion or re-weighting of an edge e = (v1 , v2 ) takes O(1) time.
Proof. Our updating process consists in performing computations on all pairs of vertices of G∗ [i−1]
whose shortest paths of length at most 8i contains a vertex of B(v1 , 2 · 8i ) or B(v2 , 2 · 8i ). This
implies that the vertices to consider are all in B(v1 , 3 · 8i ) or B(v2 , 3 · 8i ) or the extra vertex v1 or
v2 in case the update added a new vertex.
Listing these vertices can be done by growing a ball from v1 and v2 in G[i − 1] (e.g. using
Dijkstra’s algorithm).
As C[i]’s are vertex covers, we know that there are O(1) items to consider in these balls, O(1)
pairs of vertices to consider, implying that we are working on a problem of constant size.
Updating G[i] is a similar problem: edges in G[i] are shortest paths in G[i − 1] (and therefore
by induction in G). By Lemma 31, all shortest paths with at least one vertex outside the balls
are identical in both G[i] and G∗ [i], so we only need to re-compute the shortcut graph for pairs of
vertices (v4 , v4 ) for all v4 , v4 in C ∗ [i] inside the ball. This is again is a constant size problem.

24

Lemma 36. Processing an update takes O(log(U + |V |)) time.
Proof. By Lemma 30, we know that the height of the structure is at most O(log(U + |V |)), and for
each i we process the elements in O(1) time by Lemma 35.
Definition
37. Given a graph G = (V, E), and vertices v1 and v2 of V , the funnel graph FG (v1 , v2 )
S
is ∞
G[i]
∩
(B(v1 , 8i+1 ) ∪ B(v2 , 8i+1 )).
i=0
Note that in general funnel graphs are not unique, they derive from any valid set of C[i]’s.
Lemma 38. Distance is preserved in funnel graphs. For all G = (V, E), v1 , v2 ∈ V we have
dG (v1 , v2 ) = dFG (v1 , v2 ).
Proof. By construction, each edge e = (v3 , v4 ) in any G[i] has weight dG[i] (e) = dG (v3 , v4 ).
By contradiction, suppose the shortest path dFG (v1 , v2 ) in the funnel is not equal to dG (v1 , v2 )
in G.
Let j be the maximum value such that dG (v1 , v2 ) > 8j . We know that G[j] contains at least
one vertex w ∈ V (pG (v1 , v2 )), as C[j] is a vertex cover: either the shortest path is such that
maxedgeG (p(v1 , v2 )) ≤ 8j , or if there is a long edge in the shortest path, its vertices were also
included in G[j]. Note that dG (v1 , w) ≤ 8j+1 and dG (v2 , w) ≤ 8j+1 , therefore vertex w is in the
funnel graph.
We now proceed by induction, from v1 to w; let j ′ be the maximum value such that dG (v1 , w) >
′
2 · 8j . There exists a vertex w′ ̸= w on the shortest path from v1 to w, that is in G[j ′ ]. In case
where there are multiple candidates, we take the vertex closest to v1 , and we are certain that
′
dG (v1 , w′ ) ≤ 8j , and is therefore part of G[j ′ ] and of G[j ′ − 1]. That is because any subpath of
′
length at least 8j is covered by a vertex, while the path we consider is twice as long. The shortest
path from v1 to w′ is the same in G as in FG (v1 , v2 ) by induction, while the shortest path from w′
to w corresponds to edges in G[j ′ ], as w′ and w are both vertices of C[j ′ ]. This can be seen because
w is a vertex of C[j], which is a subset of C[j ′ ], as j ′ ≤ j. The path from w′ to w is therefore
in the funnel FG (v1 , v2 ), as the funnel contains the shortcut graph between all vertices in the ball
′
B(v1 , 8j +1 ). The base case is when C[j”] contains v1 , which will occur at the latest when 8j” is
smaller than the first edge of the shortest path, implying the shortest path from v1 to w” is also in
C[j”].
The symmetrical case from w to v2 is solved accordingly, concluding that we found in FG (v1 , v2 )
a path with length exactly the same as in G.
Lemma 39. Given G = (V, E), v1 , v2 ∈ V , the size of the funnel graph FG (v1 , v2 ) is O(log(U +|V |)).
Proof. In every G[i] the funnel contains the sub-graph within a constant number of balls of radius
8i+1 . We know that the number of edges and vertices of G[i] inside these balls is a constant in
a graph of constant highway dimension. As we consider O(log(U + V )) such graphs, the overall
complexity is O(log(U + V )).
Lemma 40. Given a shortest path in FG (v1 , v2 ), we can find a shortest path in G = (V, E) in
O(log(U + |V |) + p) time, where p is the number of edges in shortest path pG (v1 , v2 ).
Proof. We expand to a shortest path in G inductively: for each edge of some G[i] in our structure,
we expand it in O(l) time to the corresponding edges in G[i − 1], where l is the size of the shortest
path corresponding to that edge in G[i − 1]. Total expansion time is O(log(U + |V |) + p) where p
is the number of edges of the shortest path: at each level i we either add l edges to the path, or we
go down one level to i − 1. The induction ends when each edge corresponds to an edge of G.
25

Lemma 41. Let G be a connected graph with |V | vertices, constant highway dimension, and ratio of
smallest-to-largest edge U . Our data structure supports shortest distance queries in time O(log(|V |+
U )) and shortest path queries whose result is a path with p edges in time O(p + log(|V | + U )).
Proof. Let v1 to v2 be the vertices for which we want to compute the shortest path or the distance.
We first compute a shortest path between v1 and v2 in FG (v1 , v2 ). Note that in FG (v1 , v2 ), shortest
paths are not unique. But by Lemma 38, finding a shortest path in FG (v1 , v2 ) will give a path of
the same length as the unique shortest paths in G, and by Lemma 40, we can expand this shortest
path in O(log(U + V ) + p time to the unique shortest path pG (v1 , v2 ).
To compute the shortest paths in the funnel FG (v1 , v2 ), we proceed again by iterating on i from
0 to O(log(U + V )). By induction, we already know the shortest path from v1 to all vertices in
G[i − 1], and we determine the shortest path from v1 to all vertices in G[i], limited to the ball
B(v1 , 8i+1 ). This is a constant-size problem. We do the same for v1 and v2 and as soon as a level
contains a common vertex we maintain a best shortest path candidate.
So in O(log(U + V )) time we find a shortest path in FG (v1 , v2 ) and can determine the weight of
the shortest path, while O(log(U + V )) + p is required if we need to return the path by expanding
it.
Theorem 42. Our data structure can be computed in O(|V | log U ) time and takes O(|V | log U )
space. The data structure supports dynamic changes to the graph, edge insertions/deletions/relabeling
in time O(log(|V | + U )).

References
[1] I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension and
provably efficient shortest path algorithms. J. ACM, 63(5):41:1–41:26, 2016.
[2] I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. A hub-based labeling algorithm
for shortest paths in road networks. In P. M. Pardalos and S. Rebennack, editors, Experimental
Algorithms - 10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece,
May 5-7, 2011. Proceedings, volume 6630 of Lecture Notes in Computer Science, pages 230–
241. Springer, 2011.
[3] I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. Hierarchical hub labelings for
shortest paths. In L. Epstein and P. Ferragina, editors, Algorithms - ESA 2012 - 20th Annual
European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, volume 7501
of Lecture Notes in Computer Science, pages 24–35. Springer, 2012.
[4] I. Abraham, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. Highway dimension, shortest
paths, and provably efficient algorithms. In M. Charikar, editor, Proceedings of the TwentyFirst Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas,
USA, January 17-19, 2010, pages 782–793. SIAM, 2010.
[5] H. Bast, S. Funke, and D. Matijevic. Ultrafast shortest-path queries via transit nodes. In
C. Demetrescu, A. V. Goldberg, and D. S. Johnson, editors, The Shortest Path Problem,
Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 13-14, 2006,
volume 74 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
pages 175–192. DIMACS/AMS, 2006.

26

[6] R. Bauer, D. Delling, and D. Wagner. Experimental study on speed-up techniques for timetable
information systems. In C. Liebchen, R. K. Ahuja, and J. A. Mesa, editors, ATMOS 2007 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, November 15-16, 2007, Sevilla, Spain, volume 7 of OASIcs. Internationales Begegnungsund Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2007.
[7] J. Blum, Y. Disser, A. E. Feldmann, S. Gupta, and A. Zych-Pawlewicz. On sparse hitting
sets: From fair vertex cover to highway dimension. In H. Dell and J. Nederlof, editors, 17th
International Symposium on Parameterized and Exact Computation, IPEC 2022, September
7-9, 2022, Potsdam, Germany, volume 249 of LIPIcs, pages 5:1–5:23. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022.
[8] D. Delling and R. F. Werneck. Faster customization of road networks. In V. Bonifaci, C. Demetrescu, and A. Marchetti-Spaccamela, editors, Experimental Algorithms, 12th International
Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings, volume 7933 of Lecture
Notes in Computer Science, pages 30–42. Springer, 2013.
[9] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik,
1:269–271, 1959.
[10] Y. Disser, A. E. Feldmann, M. Klimm, and J. Könemann. Travelling on graphs with small
highway dimension. Algorithmica, 83(5):1352–1370, 2021.
[11] A. E. Feldmann. Fixed-parameter approximations for k-center problems in low highway dimension graphs. Algorithmica, 81(3):1031–1052, 2019.
[12] A. E. Feldmann, W. S. Fung, J. Könemann, and I. Post. A (1+ϵ)-embedding of low highway
dimension graphs into bounded treewidth graphs. SIAM J. Comput., 47(4):1667–1704, 2018.
[13] A. E. Feldmann and D. Saulpic. Polynomial time approximation schemes for clustering in low
highway dimension graphs. J. Comput. Syst. Sci., 122:72–93, 2021.
[14] A. E. Feldmann and T. A. Vu. Generalized k-center: Distinguishing doubling and highway
dimension. In M. A. Bekos and M. Kaufmann, editors, Graph-Theoretic Concepts in Computer
Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022,
Revised Selected Papers, volume 13453 of Lecture Notes in Computer Science, pages 215–229.
Springer, 2022.
[15] M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596–615, 1987.
[16] R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. Exact routing in large road networks
using contraction hierarchies. Transp. Sci., 46(3):388–404, 2012.
[17] A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory.
In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 156–165. SIAM,
2005.
[18] S. Gupta, A. Kosowski, and L. Viennot. Exploiting hopsets: Improved distance oracles for
graphs of constant highway dimension and beyond. In C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, editors, 46th International Colloquium on Automata, Languages, and
27

Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages
143:1–143:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
[19] R. J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for
road networks. In L. Arge, G. F. Italiano, and R. Sedgewick, editors, Proceedings of the Sixth
Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic
Algorithmics and Combinatorics, New Orleans, LA, USA, January 10, 2004, pages 100–111.
SIAM, 2004.
[20] M. Holzer, F. Schulz, and D. Wagner. Engineering multi-level overlay graphs for shortest-path
queries. In R. Raman and M. F. Stallmann, editors, Proceedings of the Eighth Workshop on
Algorithm Engineering and Experiments, ALENEX 2006, Miami, Florida, USA, January 21,
2006, pages 156–170. SIAM, 2006.
[21] A. Jayaprakash and M. R. Salavatipour. Approximation schemes for capacitated vehicle routing
on graphs of bounded treewidth, bounded doubling, or highway dimension. ACM Trans.
Algorithms, 19(2):20:1–20:36, 2023.
[22] A. Kosowski and L. Viennot. Beyond highway dimension: Small distance labels using tree
skeletons. In P. N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January
16-19, pages 1462–1478. SIAM, 2017.
[23] U. Lauther. An experimental evaluation of point-to-point shortest path calculation on road
networks with precalculated edge-flags. In C. Demetrescu, A. V. Goldberg, and D. S. Johnson,
editors, The Shortest Path Problem, Proceedings of a DIMACS Workshop, Piscataway, New
Jersey, USA, November 13-14, 2006, volume 74 of DIMACS Series in Discrete Mathematics
and Theoretical Computer Science, pages 19–39. DIMACS/AMS, 2006.
[24] S. Pettie and V. Ramachandran. Computing shortest paths with comparisons and additions. In
D. Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete
Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 267–276. ACM/SIAM, 2002.
[25] P. Sanders and D. Schultes. Engineering highway hierarchies. ACM J. Exp. Algorithmics,
17(1), 2012.
[26] M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.

28