3 July 2015

Eva Rotenberg awarded the Danish Master Thesis of The Year Prize in Computer Science

Eva Rotenberg, Graph algorithms and data structures

Eva Rotenberg received this year's Master Thesis of The Year Prize, awarded by The Danish Society for Computer Science and DANISH IT, for her Master's thesis on the subject of dynamic graphs. The thesis has resulted in a data structure which allows a user to insert and delete edges in a planar graph without changing its property.

On Thursday, June 18th, this year's Master's Thesis of The Year award ceremony was held in cooperation between The Danish Society for Computer Science and DANISH IT, and we are proud to announce this year's winner, Eva Rotenberg. She was nominated for her Master's thesis Maintaining alterable planar embeddings of dynamic graphs, which deals with the problem of inserting and deleting edges in a planar graph.

The new function - Flip

A planar graf is a graph that can be embedded in the plane such that no edges intersect, except for in the endpoints. A planar graph can often be drawn in several different ways in the plane. Each of these are called an embedding. The new data structure developed by Eva allows for the insertion and deletion of edges in the graph without changing the embedding, and in a way so that the graph is still planar. This has previously been supported by a similar data structure from 1993.

As something new, the data structure allows the user to change the embedding, that is the way the graph is drawn in the plane. To change the embedding, a flip is performed where a subgraph is flipped upside down. In order to perform the flip, the subgraph must be connected to the rest of the graph at two points or less. If a graph can be drawn in several different ways in the plane, you can get from one embedding to another by performing a sequence of these flips.

High technical level

In the nomintation for the award, Eva was especially praised for the high technical level of the thesis, but also for her effective and accessible presentation of the subject.

It was emphasized that it was impressive that the new funktion, flip, could be performed in the same fast time complexity, O((log n)^2) as the previous data structure from 1993, as well as the additional edge insertions and deletions with the same time complexity, as well as the fact that her results were on par with absolute top researchers, ie. Henzinger and Fredman.

Good level across the board

When we met Eva, she told us that she was very proud to be nominated for the award:

"The other nominated theses were all very exciting and good," she explained and continued: "There were theses within a wide range of subjects from universities all across Denmark."

Since the completion of her thesis in January last year, Eva has continued working with the subject in cooperation with computer science student Jacob Holm, which has resulted in an article on the conference STACS. Currently, she is employed as a Ph.D. student under supervision of Mikkel Thorup and Christian Wulff-Nilsen in the APL Section at DIKU.

Previous winners

It's not the first time DIKU students have won the Master's Thesis Award. In 2008 three students shared the award, James Avery with the thesis The Generalized Sturmian Method: Development, Implementation and Applications in Atomic Physics, and René Truelsen and Kristine Slot with the thesis Content-aware video editing in the temporal domain. The year before, Mohammad Jowkar won it for his thesis on Cell-processors.

Likewise, her colleague in the APL Section, Rasmus Fonseca, won in 2009 for his thesis with the title Ab Initio Protein Structure Prediction using Bezier Curve Representation.

The first winner ever back in 1994, Klaus Harbo, is also from DIKU, and there have been several winners from DIKU in the years inbetween.