Planarity of a Dynamic Graph

“Fully-dynamic Planarity Testing in Polylogarithmic Time” by Jacob Holm from BARC-DIKU and Eva Rotenberg from DTU, alumni from DIKU.
Click here for the arXiv version.

One of the classical problems in graph theory is whether a given graph is "planar", i.e. if it can be drawn in the plane without crossing lines, and how to produce such a drawing when it exists. Planar or almost planar graphs appear in many applications, e.g road networks and computer chip (VLSI) design. A simple example of the problem from popular culture is commonly known as the "Three Utilities Problem", a logic puzzle that already in 1913 was described as being "old as the hills". We have known a purely mathematical classification of planar graphs since 1930 (Kuratowski's Theorem), and we have had efficient linear-time algorithms for deciding whether a given graph is planar since 1974 (Hopcroft and Tarjan).  In many graph applications the graph in question is "dynamic", i.e. it changes over time e.g. by the insertion and deletion of edges. E.g. road networks change both due to accidents and construction work, and in a CAD program for chip design you'd want to be able to insert and delete wires and components. It turns out that for dynamic graph problems it is often possible to build some data structure that can be used to recompute the answer after each change to the graph much faster than recomputing the answer from scratch. This is also true for the planarity testing/planar drawing problem. 

In my recent SODA'20 paper with Eva Rotenberg (see https://arxiv.org/abs/1910.09005 for a full version), we showed that there is a way of defining and maintaining a "good" drawing for each planar graph such that each edge deletion or insertion that leaves the graph planar requires only O(log n) "local changes" (called "flips") to the drawing in the worst case. Here, a "flip" consists of cutting out a piece of the drawing by cutting through at most two vertices, and replacing the piece with its mirror image. Unfortunately, while this result holds for both edge deletions and insertions (as long as the graph stays planar), it only gives a way to actually find these flips during insertions, leading to an insertions-only algorithm for planarity testing and maintaining a planar drawing with a worst case running time of O(log³ n) time per edge insertion.

For fully-dynamic planarity testing/planar drawing, the best previously known algorithm is from 1996 and uses roughly O(√n) time per update on average. I have worked on this problem since 1998 (originally together with Kristian de Lichtenberg right after presenting our masters thesis at STOC'98), and much of my published research since then has been inspired by and related to this problem. Eva joined the effort in 2014, and we have finally found a much better solution using only O(log³ n) time per update on average. Even better, the new algorithm allows you to manually make any desired flips to the current drawing (in O(log² n) time per flip), requires no flips during deletion, and essentially just finds the shortest sequence of flips needed each time an edge is inserted. This makes the algorithm ideal for CAD-like applications, where a user needs to be in control of the drawing, but may need assistance when inserting an edge. The proof that such a naive algorithm even works builds heavily on the understanding of the structure of good drawings gained in the SODA'20 paper (in fact we were afraid to be scooped when we realized how close the SODA paper came to proving this), but the actual algorithm is oblivious to this structure. 

This result is of course a huge personal victory for us, but to quote one of our anonymous reviewers: "The biggest positive of this paper is surely the strength of the result and the fact that the previous best data structure for this problem dates back to 1996. The problem it considers is very natural and one of the first that come to my mind when I think of properties I would like to maintain in a dynamic graph. The paper makes it easy to follow the general idea of the approach and does a good job of explaining the greedy algorithm used to find the necessary flips."