A New Algorithm for Graph Crossings, Hiding in Plain Sight

This past October, as Jacob Holm and Eva Rotenberg were thumbing through a paper they’d posted a few months earlier, they realized they had been sitting on something big.

For decades computer scientists had been trying to develop a fast algorithm for determining when it’s possible to add edges to a graph so that it remains “planar,” meaning none of its edges cross each other. But the field had been unable to improve on an algorithm published over 20 years ago.

Holm and Rotenberg were surprised to find that their paper contained the insight needed to do a lot better. It “solved one of the major stumbling blocks we had with actually getting a real algorithm,” said Holm, a computer scientist at the University of Copenhagen. “We might have given the whole thing away.”

The two rushed to draft a new paper. They presented it in June at the ACM Symposium on Theory of Computing, where they detailed an exponentially better method for checking whether a graph is planar.

“The new algorithm is a remarkable tour de force,” said Giuseppe Italiano, a computer scientist at Luiss University and a co-author of the 1996 paper describing what is now the second-fastest algorithm. “When I co-authored that paper, I didn’t think that this could happen.”

Graphs are collections of nodes connected by edges. They can be used to represent everything from a social network to road systems to the electrical connections on a circuit board. In circuit boards, if the graph isn’t planar, it means that two wires cross each other and short-circuit.

As early as 1913, planar graphs came up in a brainteaser called the three-utilities problem, published in The Strand Magazine. It asked readers to connect three houses to three utilities — water, gas and electricity — without crossing any of the connections. It doesn’t take long to see that it can’t be done.

But it’s not always immediately obvious whether more complicated graphs are planar. And it’s even harder to tell whether a complicated planar graph stays planar when you start adding edges as you might when planning a new stretch of highway.

Computer scientists have been searching for an algorithm that can quickly determine whether you can make the desired change while keeping the graph planar and without checking every single part of the graph when only one small part is affected. The 1996 algorithm required a number of computational steps that was roughly proportional to the square root of the number of nodes in the graph.

“[It’s] much better than just doing it from scratch each time, but it’s not really good,” said Holm.

The new algorithm checks planarity in a number of steps proportional to the cube of the logarithm of the number of nodes in the graph — an exponential improvement. Holm and Rotenberg, a computer scientist at the Technical University of Denmark, achieved the speedup by taking advantage of a special property of planar graphs that they discovered last year.

To understand their method, the first thing to notice is that the same planar graph can be drawn multiple ways. In these different drawings, the connections remain the same, but the edges might be in different positions relative to one another.

For example, you can change drawing A into drawing B by flipping the triangle made by nodes 1, 2 and 3 over the edge connecting nodes 2 and 3. The top section of drawing B can also be reflected over nodes 4 and 5 to produce drawing C. The drawings look different, but they’re the same graph.

Now imagine that you want to insert a new edge connecting two nodes in a planar graph, say nodes 1 and 6 in the example below. To do so, you’re going to perform a series of flips. From the starting position on the left it takes two flips to move node 1 into a space where it can be connected to node 6 without crossing any other edges.

In their 2019 paper Holm and Rotenberg found that some drawings provide a more advantageous starting position for inserting an edge than others. These “good” drawings are only a few flips away from accepting the edge without breaking planarity.

What they belatedly recognized in October was that a flip that brings you closer to being able to add a new edge also brings the graph closer to resembling one of the good drawings they’d already identified. By showing that a series of flips inevitably moves a graph toward a favorable drawing, the new algorithm puts a backstop on the number of flips you could possibly need to perform before finding a way to insert an edge (provided the insertion is possible at all).

“We very quickly realized that with this new analysis, a conceptually very, very simple algorithm will solve the problem,” said Holm.

The new algorithm performs flips one at a time, searching for a solution. Eventually, one of two things happens: Either the algorithm finds a way to insert the desired edge, or the next flip undoes the previous flip — at which point the algorithm concludes there’s no way to add the edge.

“We call this the lazy-greedy [algorithm],” Rotenberg explained. “It only does the changes necessary to accommodate the edge.”

Their new method approaches — but doesn’t quite achieve — the performance of the best possible algorithm (or lower bound) for this kind of problem. The new algorithm also has to work through too many steps for most real-world applications, where the relevant graphs are usually simple enough to check with brute-force methods.

But for Holm and Rotenberg, the speed of the algorithm is less important than the insights that accelerated it. “Out of that understanding comes something fast,” said Rotenberg.

And Italiano thinks it may eventually help with real-world applications. “[It’s] likely to have, sooner or later, an impact also outside computer science and mathematics,” he said.

As for when an even faster algorithm will come along, no one knows. It could require a whole new breakthrough, or the secret ingredient may already be out there, waiting in a stack of old research papers.

Correction: September 17, 2020

The second figure in the story used two flips to insert the desired edge when only one was necessary. It has been revised to require two flips to insert the edge.