Algorithms for Planar Graphs and Graphs in Metric Spaces

Publikation: Bog/antologi/afhandling/rapport › Ph.d.-afhandling › Forskning

Algorithms for network problems play an increasingly important

role in modern society. The graph structure of a network is an abstract

and very useful representation that allows classical graph algorithms,

such as Dijkstra and Bellman-Ford, to be applied. Real-life networks

often have additional structural properties that can be exploited. For

instance, a road network or a wire layout on a microchip is typically

(near-)planar and distances in the network are often defined w.r.t. the

Euclidean or the rectilinear metric. Specialized algorithms that take

advantage of such properties are often orders of magnitude faster than

the corresponding algorithms for general graphs.

The first and main part of this thesis focuses on the development of

efficient planar graph algorithms. The most important contributions

include a faster single-source shortest path algorithm, a distance oracle

with subquadratic preprocessing time, an O(n log n) time algorithm

for the replacement paths problem, and a min st-cut oracle with nearlinear

preprocessing time. We also give improved time bounds for

computing various graph invariants such as diameter and girth.

In the second part, we consider stretch factor problems for geometric

graphs and graphs embedded in metric spaces. Roughly speaking,

the stretch factor is a real value expressing how well a (geo-)metric

graph approximates the underlying complete graph w.r.t. distances.

We give improved algorithms for computing the stretch factor of a

given graph and for augmenting a graph with new edges while minimizing

stretch factor.

The third and final part of the thesis deals with the Steiner tree

problem in the plane equipped with a weighted fixed orientation metric.

Here, we give an improved theoretical analysis of the strength

of pruning techniques applied by many Steiner tree algorithms. We

also present an algorithm that computes a so called Steiner hull, a

structure that may help in the computation of a Steiner minimal tree.

Originalsprog	Engelsk

ID: 21430290