**
Dimitrios
Skrepetos,
PhD
candidate***
David
R.
Cheriton
School
of
Computer
Science*

This
thesis
studies
shortest
paths
in
geometric
intersection
graphs,
which
can
model,
among
others, *ad-hoc *communication
and
transportation
networks.
First,
we
consider
two
classical
problems
in
the
field
of
algorithms,
namely,
Single-Source
Shortest
Paths
(SSSP)
and
All-Pairs
Shortest
Paths
(APSP):
given
a
graph,
we
want
to
compute
the
shortest
paths
from
one
vertex
to
all
other
vertices
(for
the
former)
or
the
shortest
path
between
every
pair
of
vertices
(for
the
latter).

Although there is a vast literature for these problems in many graph classes, the case of geometric intersection graphs has been only partially addressed.

In unweighted unit-disk graphs, we show that, after presorting the disk centers with respect to their coordinates, we can solve SSSP in linear time. Furthermore, we give the first (slightly) subquadratic-time APSP algorithm by using our new SSSP result, bit tricks, and a shifted-grid-based decomposition technique.

In unweighted, undirected geometric intersection graphs, we present a simple general technique that reduces APSP to static, offline intersection detection. Consequently, we give fast APSP algorithms for intersection graphs of arbitrary disks, axis-aligned line segments, arbitrary line segments, d-dimensional axis-aligned boxes, and d-dimensional axis-aligned unit hypercubes. We also provide a near-linear-time SSSP algorithm for intersection graphs of axis-aligned line segments, by a reduction to dynamic orthogonal point location.

Then we consider two problems that have received considerable attention lately. The first is that of computing the diameter of a graph, i.e., the longest shortest-path distance between any two vertices. In the second, we want to preprocess a graph into a data structure, called distance oracle, such that the shortest path (or its length) between any two query vertices can be found quickly. Since these problems are often too costly to solve exactly, we study their approximate versions.

Following a long line of research, we employ Voronoi diagrams to compute a (1/epsilon)-approximation of the diameter of an undirected, non-negatively-weighted planar graph in time near-linear on the input and polynomial on 1/epsilon (the previously best solution had exponential dependency on the latter). Using similar techniques, we can also construct the first (1+epsilon)-approximate distance oracles with similar preprocessing time and space and only O(log(1/epsilon)) query time.

In weighted unit-disk graphs, we present the first near-linear-time (1+epsilon)-approximation algorithm for the diameter (and for other related problems, such as the radius and the bichromatic closest pair), by combining techniques from computational geometry (well-separated pair decompositions) and planar graphs (shortest-path separators). We also show how to extend our approach to obtain O(1)-query-time (1+epsilon)-approximate distance oracles with near-linear preprocessing time and space, and then apply these, along with additional ideas, to build, in truly subcubic time, a data structure for the (1+epsilon)-approximate All-Pairs Bounded-Leg Shortest Paths (apBLSP) problem.