A few Danish computer scientists have solved a years-long mathematical puzzle that lay dormant for decades, after researchers made insignificant progress since the 1990s.
The abstract problem in question is part of what is called graph theory, and specifically deals with the challenge of finding an algorithm to solve the planarity of a dynamic graph. That might sound a little daunting, so if your graphics theory is a little quieter, there’s a much more fun and accessible way to think about the same inherent ideas.
Going as far as 1913 – although the mathematical concepts can probably be traced much further back – a puzzle called the three utility problem was published.
Just imagine that there are three houses in a row that you can draw on a piece of paper. Among them, you would probably draw three separate utilities: water, gas, and electricity.
Three utilities with one line crossing. (CMG Lee / Wikimedia Commons / CC BY-SA 4.0)
The challenge is to draw lines on this simple graph, by connecting the three utilities to each house. But there is a problem: none of the lines (a total of nine) on the paper may cross each other. Can you think of a way to do it all without crossing any of the links?
In the most conventional sense – on a plain, two-dimensional sheet of paper, as an example of a flat graph – it is not possible to solve the three utility problem. Uncomfortable though it may be, not all of these homes can get their connections.
But the three help problem is not a puzzle that needs to be solved so much, instead an example of how some types of graphing networks are not planned – that is able to have edges (lines) that have their different vertices (houses and utilities) ) connect without crossing the lines.
When dealing with more complex graphs involving more vertices, Kuratowski’s proposition helps mathematicians determine whether graphs are planned or not, and since the 1970s, researchers have also developed algorithms to do the same thing faster. .
However, after one definitive algorithmic progress in the 1990s, no substantial progress was made in this area, at least not with regard to algorithms that can solve for dynamic (changing) graphs.
Fast forward to last year, and computer scientists Jacob Holm of the University of Copenhagen and Eva Rotenberg of the Technical University of Denmark were slaves to the problem.
“We had almost given up on getting the last piece and solving the riddle,” Holm says. “We estimate that there would be another five years of work, at best, before we could solve the puzzle.”
It was at this point, almost by accident, they realized that they had already effectively solved most of the problem in another piece of research – a pre-print paper on related planning concepts, which the couple released online in 2019.
With the already published hidden solution, the couple shrugged in the following weeks, writing a formal proof of their improvement to the graphing algorithm, which had not seen any improvement since the 1990s.
“We spent five to six weeks working non-stop on the article. And it ended up filling out more than 80 pages,” says Rotenberg.
The results, now published, provide an algorithm that takes the least computable time to resolve the question of whether a dynamic graph – subject to insertions and deletions of edges connecting its vertices – can support a flat embedding. (In simple terms, or it could be drawn on a piece of paper without lines crossed out.)
It’s a big improvement, because the same difficulties are present in something as conceptually simple as the three auxiliary problems become much more inaccessible in fields like microchip design and road planning, where many more cornerstones are involved than just three houses and three utilities.
“It turns out that for dynamic graphing problems, it’s often possible to build some data structure that can be used to compute the response to each change to the graph much faster than calculating the response from scratch,” explains Holms.
“This result is obviously an enormous personal victory for us.”
The findings are reported in STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.
.
