PhD defense by Eva Rotenberg: Algorithms and Data Structures for Graphs – Københavns Universitet

PhD defense by Eva Rotenberg: Algorithms and Data Structures for Graphs

Title

Algorithms and Data Structures for Graphs

Abstract

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. 

Assessment Committee

  • 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

Academic supervisors

  • 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 phdadmin@di.ku.dk