The two computer scientists, assistant professor Jacob Holm of UCPH and associate professor Eva Rotenberg of DTU almost gave away their solution in the summer of 2019, after submitting a research article that became the forerunner of the article in which she definitively solves the mathematical riddle . Credit: University of Copenhagen
Researchers thought they were five years away from solving a 1980s math puzzle. In reality, and without knowing it, they had almost cracked the problem.
Researchers from the University of Copenhagen and the Technical University of Denmark (DTU) thought they were five years away from solving a 1980s math puzzle. In reality, and without knowing it, they had almost cracked the problem and had just given much of the solution in a research article. The solution could be used to improve tomorrow’s phones and computers.
A real brain teaser. That is how one can safely describe this mathematical problem in the discipline of graph theory. Two mathematicians from the Department of Computer Science and the University of Copenhagen of the University of Copenhagen have now solved a problem with which the fastest and smartest in the world since the 1980s have wrestled.
The two computer scientists, assistant professor Jacob Holm of UCPH and associate professor Eva Rotenberg of DTU almost gave away their solution in the summer of 2019, after submitting a research article that became the forerunner of the article in which she definitively solves the mathematical riddle .
“We had almost given up on getting the last piece and solving the riddle. We thought we had a small result, one that was interesting but in no way solved the problem. We estimate that there will be at least another five years of work before we can solve the puzzle, ”explains Jacob Holm, part of BARC, the algorithm section at UCPH’s Computer Science department.
In 1913, a forerunner of the now solved mathematical conundrum was published in “The Strand Magazine” as “The Three Utilities Problem”. It caused the readers of the magazine to scratch their heads and think. In the problem, each of three houses must have water, gas and electricity, while the ‘lines’ between the houses and water, electricity and gas may not cross each other – which is not possible. Credit: University of Copenhagen
A solution between the lines
Simply put, the puzzle is about how to connect a number of points in a graph without crossing the lines that connect them. And how, with a mathematical calculation – an algorithm – you can make changes in an extensive “graphing network” to ensure that no lines intersect without having to start over. Features that can be used for, among other things, the construction of immense road networks such as the small interiors of computers, whereby electrical circuits on steering stations may not cross.
Jacob Holm has been interested in the mathematical conundrum since 1998, but the answer was only revealed while the two researchers were reading through their already submitted research article. In the meantime, the researchers heard about a new mathematical technique that they realized could be applied to the problem.
“While reading our research article, we suddenly realized that the solution was in front of our eyes. Our next reaction was ‘oh no – we shot ourselves in the foot and gave the solution,’ says associate professor Eva Rotenberg of DTU.
Could be used for computer electronics
This is when the two researchers were busy writing the research paper and tying loose ends to solve the conundrum that Holm had been working intermittently since 1998.
‘We worked on the article non-stop for five to six weeks. And it ended up filling more than 80 pages, ”says Eva Rotenberg.
Fortunately, no one came up with the solution and the two researchers were able to present their results at the most important theoretical computer science conferences, which were meant to be held in Chicago, but actually ended.
So, what solution can be used for this mathematical conundrum? The two researchers do not know for sure, but they have a few suggestions.
“Our research is basic research, so we rarely know where it will end up being used. Even from the beginning, we find applications difficult to think of, “says Jacob Holm, who added:
“The design of microchips and circuit boards, found in all electronics, could be an area where our end ends up being used. When drawing wires on a circuit board, they should never cross each other. Otherwise, short circuits will occur. The same goes for microchips, which contain millions of transistors and for which you need to have a graphite drawing. ”
About graph theory
A GRAPH is a very simple construction that is used to model things that can be described as objects and the connections between them. Graphics theory is both an area of mathematics and an important tool in computer science.
In this context, a graph can be illustrated by a diagram consisting of a number of points (nodes, vertices) connected by a number of lines (edges). Each edge is illustrated as a line (as a curved piece) with nodes as two endpoints.
About the solution
There are two types of updates in dynamic graphs: one can delete an edge and you can insert a new edge. These two operations must be performed by the user, while an algorithm keeps track of the network at all times. This is the algorithm that the researchers found the recipe for.
Reference: “Fully dynamic planarity test in polylogarithmic time” by Jacob Holm and Eva Rotenberg, 10 December 2019, Computer Science> Data Structures and Algorithms.
arXiv: 1911.03449
