Getting to work in the morning before the first meeting starts or getting back home again before the day care closes, can be a challenge to everyone’s work/life balance. But what happens, when the trails are blocked so your train doesn’t go or if an accident blocks the motorway? Not only does your time schedule run wild, but is there an alternative route? Will this mean that everyone going from Lyngby to Amager have to take the same bus? And how many more accidents need to happen before you get completely isolated from your destination and may give up on arriving?
These fundamental questions motivate Eva Rotenberg and her research in dynamic graph connectivity. Eva is assistant professor in DTU Compute’s AlgoLog section, and her research revolves around dynamic graphs. What makes these graphs dynamic is how they are subject to something being taken away, or something being added. The dynamic graphs can be used in many different fields like communication networks, electronic circuits, the internet, social networks, and traffic. Eva works on superfast algorithms for pointing out the “weak points” crucial to the connectivity of the entire network.
Getting from a to b
The algorithm Eva presents is used in planar networks with no crossing segments. In the article ‘Decremental SPQR-trees for Planar Graphs’ she and her co-authors invented a superfast algorithm that can handle large networks and keep track of certain types of cuts, or weak points, along the way. This can be used to e.g. count the number of routes for your way home (b) from work (a), when one route (e) in the network is taken out (see illustration above). It locates the weak points (x and y) where the network is about to fall apart. “Our algorithm answers instantly, i.e. in constant time, to whether there are 0, 1, 2, or at least 3 non-crossing routes between any given pair of locations, while efficiently handling that road segments become inaccessible. Our average-time for updating the information is an exponential improvement over the previous best algorithm, dating back to ’93”, Eva explains.
As soon as the networks have crossing segments, or segments that were malfunctioning become repaired and are added back in, it is hard to reach the at least 3 non-crossing routes with superfast algorithms. So, the work is ongoing, as is Eva’s fascination with dynamic graphs. “When graphs model so many things in the real world, and the real world is such an ever-changing place, it is certainly important to understand how graphs behave as they change over time.”
Eva co-authored the article ‘Decremental SPQR-trees for Planar Graphs’ with Jacob Holm (KU), Giuseppe F. Italiano (University of Rome Tor Vergata), Adam Karczmarz (University of Warsaw), and Jakub Lacki (Google Research). The article was applauded at the 26th Annual European Symposium on Algorithms (ESA'18) in Helsinki, Finland, and awarded ESA’18 track A Best Paper Award. Congratulations!
The article: "Decremental SPQR-trees for Planar Graphs, by Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, 28 June 2018
The award: ESA’18 track A Best Paper Award was given at the 26th Annual European Symposium on Algorithms (ESA'18) in Helsinki, Finland. ESA is one of the premier conferences on algorithms and covers research in all aspects of the design, analysis, engineering, and application of algorithms.
The illustration: When the road segment e becomes inaccessible there are no longer 3 but only 2 non-crossing routes from the point a to the point b; all routes must go through either x or y.