TY - BOOK

T1 - Algorithms for Planar Graphs and Graphs in Metric Spaces

AU - Wulff-Nilsen, Christian

PY - 2010

Y1 - 2010

N2 - Algorithms for network problems play an increasingly importantrole in modern society. The graph structure of a network is an abstractand very useful representation that allows classical graph algorithms,such as Dijkstra and Bellman-Ford, to be applied. Real-life networksoften have additional structural properties that can be exploited. Forinstance, 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. theEuclidean or the rectilinear metric. Specialized algorithms that takeadvantage of such properties are often orders of magnitude faster thanthe corresponding algorithms for general graphs.The first and main part of this thesis focuses on the development ofefficient planar graph algorithms. The most important contributionsinclude a faster single-source shortest path algorithm, a distance oraclewith subquadratic preprocessing time, an O(n log n) time algorithmfor the replacement paths problem, and a min st-cut oracle with nearlinearpreprocessing time. We also give improved time bounds forcomputing various graph invariants such as diameter and girth.In the second part, we consider stretch factor problems for geometricgraphs and graphs embedded in metric spaces. Roughly speaking,the stretch factor is a real value expressing how well a (geo-)metricgraph approximates the underlying complete graph w.r.t. distances.We give improved algorithms for computing the stretch factor of agiven graph and for augmenting a graph with new edges while minimizingstretch factor.The third and final part of the thesis deals with the Steiner treeproblem in the plane equipped with a weighted fixed orientation metric.Here, we give an improved theoretical analysis of the strengthof pruning techniques applied by many Steiner tree algorithms. Wealso present an algorithm that computes a so called Steiner hull, astructure that may help in the computation of a Steiner minimal tree.

AB - Algorithms for network problems play an increasingly importantrole in modern society. The graph structure of a network is an abstractand very useful representation that allows classical graph algorithms,such as Dijkstra and Bellman-Ford, to be applied. Real-life networksoften have additional structural properties that can be exploited. Forinstance, 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. theEuclidean or the rectilinear metric. Specialized algorithms that takeadvantage of such properties are often orders of magnitude faster thanthe corresponding algorithms for general graphs.The first and main part of this thesis focuses on the development ofefficient planar graph algorithms. The most important contributionsinclude a faster single-source shortest path algorithm, a distance oraclewith subquadratic preprocessing time, an O(n log n) time algorithmfor the replacement paths problem, and a min st-cut oracle with nearlinearpreprocessing time. We also give improved time bounds forcomputing various graph invariants such as diameter and girth.In the second part, we consider stretch factor problems for geometricgraphs and graphs embedded in metric spaces. Roughly speaking,the stretch factor is a real value expressing how well a (geo-)metricgraph approximates the underlying complete graph w.r.t. distances.We give improved algorithms for computing the stretch factor of agiven graph and for augmenting a graph with new edges while minimizingstretch factor.The third and final part of the thesis deals with the Steiner treeproblem in the plane equipped with a weighted fixed orientation metric.Here, we give an improved theoretical analysis of the strengthof pruning techniques applied by many Steiner tree algorithms. Wealso present an algorithm that computes a so called Steiner hull, astructure that may help in the computation of a Steiner minimal tree.

M3 - Ph.D. thesis

BT - Algorithms for Planar Graphs and Graphs in Metric Spaces

PB - Museum Tusculanum

ER -