PhD defense by Eva Rotenberg: Algorithms and Data Structures for Graphs
Algorithms and Data Structures for Graphs
A graph consists of a set of vertices and a set of edges between vertices. Graphs are a popular mathematical model for road maps, communication networks, electrical circuits, social networks, disease transmission networks, job assignments, resource allocation, and more.
A special class of graphs are planar graphs, which are those that can be drawn on a piece of paper without any pair of edges crossing. For planar graphs where each edge can only be traversed in one direction, a fundamental question is whether there is a route from vertex A to vertex B in the graph. We show how such a graph can be represented in a very compact way (linear space), such that we can still answer very fast (constant time) to questions of the form: "is there a path from A to B?"
When edges can be traversed in either direction, the graph is connected if for any two vertices of the graph, there is a path between them. However, for many practical purposes, e.g. in communication networks, it is important for the graph to be highly connected: If the removal of few vertices or edges would disconnect the graph, this points to a vulnerability in the network; an indication that the network connectivity may be about to break down. This is particularly challenging, because in the real world, graphs rarely stay as they are: Links in the communication network fail, a road becomes inaccessible or slow, or — social networks change all the time. We show how to represent a graph in a compact way, such that we can give fast answers to questions of the form: "Is there an edge such that all paths between A and B go via that edge?" and which can quickly be updated when edges are inserted or deleted.
We further show how to represent a planar graph such that we can quickly update our representation when an edge is deleted, and such that questions of the form: "How many non-crossing paths are there between A and B?" can quickly (in constant time) be answered by: "None", "One", "Two", or "At least 3".
Higher connectivity also has theoretical applications. Indeed, we study the problem of finding a tour that visits every vertex exactly once, and such that two consecutive vertices are at most 2 edges apart. For general graphs, it is NP-hard even to decide if such a tour exists, but when the graph is highly connected in the sense that it does not contain a vertex whose removal would disconnect it, we give a linear time algorithm for outputting such a tour. The previous best algorithm for this had quadratic running time.
Finally, we study online bipartite graphs. Imagine a number of servers are given in advance, and then, clients arrive one by one. Each client can only be served by a subset of the servers, and each server can only serve a fixed number of clients. We want to at all times serve as many clients at possible, but then, we may sometimes need to reassign a client to a different server. We show that very few reassignments are necessary.
- Chairman: Professor Jakob Grue Simonsen, Department of Computer Science, University of Copenhagen
- Professor Valerie King, Department of Computer Science, University of Victoria, Canada
- Professor Uri Zwick, Department of Computer Science, Tel Aviv University, Israel
- Professor Mikkel Thorup, Department of Computer Science, University of Copenhagen
- Associate Professor Christian Wulff-Nilsen, Department of Computer Science, University of Copenhagen
For an electronic copy of the thesis, please contact email@example.com