More Efficient Algorithms for Graph Orientations and Geometric Cover

PhD defence, Wednesday 29 November 2017, Edvin Berglin.

2017.11.29 | Trine Berndt Turtiainen Scheelke

Edvin Berglin

During his studies, Edvin researched algorithms for storage methods for abstract networks ("graphs") with provable efficiency guarantees, that provide both fast queries into the data structure as well as fast updates when the structure of the network is modified by some outside event. One such network is the graph of all friendships between the two billion users on Facebook, which is modified many times per second as new friendships are established and old ones are removed. Edvin also made contributions towards faster algorithms for geometric cover problems, i.e. covering points by drawing lines, circles or other types of geometric shapes, and staying within a limited budget for the total number of shapes drawn. Problems of this kind are inherent to the layout of integrated circuits, and improved algorithms can aid engineers in designing more efficient chips.

The PhD degree was completed at the Department of Computer Science, Science and Technology, Aarhus University.

This résumé was prepared by the PhD student.

Time: Wednesday 29 November 2017 at 13.00
Place: Building 5342, room 333 (Ada-333), Department of Computer Science, Aarhus University, Åbogade 34, 8200 Aarhus N.
Title of dissertation: Geometric covers, graph orientations, counter games
Contact information:
Edvin Berglin, e-mail:, tel.: +45 53810424
Members of the assessment committee:
Associate professor Christian Wulff-Nilsen, Department of Computer Science, University of Copenhagen (DIKU)
Associate professor Lukasz Kowalik, Institute of Informatics, University of Warsaw
Associate professor Ira Assent (chair), Department of Computer Science, Aarhus University
Main supervisor:
Professor Gerth Stølting Brodal, Department of Computer Science, Aarhus University
Language: The PhD dissertation will be defended in English

The defence is public.
The dissertation is available for reading at the Graduate School of Science and Technology/GSST,
Ny Munkegade 120, building 1520, rooms 128-134, 8000 Aarhus C.

PhD defence
Comments on content: 
Revised 22.03.2018