Graph theory: Solution to '3 utilities problem' could lead to better computers

Jacob Holm and Eva Rotenberg

The two computer scientists, Assistant Professor Jacob Holm of UCPH and Associate Professor Eva Rotenberg of DTU almost gave their solution away in the summer of 2019, after submitting a research article that became the precursor to the article in which they finally solved the math riddle.

A veritable brain teaser. That's how one can safely describe this mathematical problem in the discipline of graph theory. Two mathematicians from the University of Copenhagen's Department of Computer Science and DTU have now solved a problem that the world's quickest and most clever have been struggling with since the 1980's.

The two computer scientists, Assistant Professor Jacob Holm of UCPH and Associate Professor Eva Rotenberg of DTU almost gave their solution away in the summer of 2019, after submitting a research article that became the precursor to the article in which they finally solved the math riddle.

"We had nearly given up on getting the last piece and solving the riddle. We thought we had a minor result, one that was interesting, but in no way solved the problem. We guessed that there would be another five years of work, at best, before we would be able to solve the puzzle," explains Jacob Holm, who is a part of BARC, the algorithm section at UCPH's Department of Computer Science.

The three utilities problem

In 1913, a precursor to the now solved mathematical conundrum was published in "The Strand Magazine" as "The Three Utilities Problem." It caused the magazine's readers to scratch their heads and ponder. In the problem, each of three cottages 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.

A solution between the lines

Simply put, the puzzle is about how to connect a number of points in a graph without allowing the lines connecting them to cross. And how, with a mathematical calculation -- an algorithm -- you can make changes to an extensive "graph network" to ensure that no lines intersect without having to start all over again. Properties that can be used for, among other things, building immense road networks or the tiny innards of computers, where electrical circuitry on circuit boards 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 novel mathematical technique that they realized could be applied to the problem.

"While reading our research article, we suddenly realized that the solution was before our eyes. Our next reaction was 'oh no -- we've shot ourselves in the foot and given away the solution,' says Associate Professor Eva Rotenberg of DTU.

About graph theory

A GRAPH is a very simple construction used to model things that can be described as objects and the connections between them. Graph 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) associated with a number of lines (edges). Each edge is illustrated as a line (or curved piece) with nodes as its two endpoints.

About the solution

There are two kinds of updates in dynamic graphs: One can delete an edge and you can insert a new edge. These two operations must be made by the user, while an algorithm keeps track of the network's drawing at all times. This is the algorithm that the researchers have found the recipe for.

Could be used for computer electronics

This is when the two researchers got busy writing the research paper and tying up loose ends to solve the conundrum that Holm had been working on 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 beat them to the solution and the two researchers were able to present their results at the main theoretical computer science conferences, which were meant to be held in Chicago, but ended up being held virtually.

So, what can the solution to this mathematical conundrum be used for? The two researchers don't know for sure, but they have a few suggestions.

"Our research is basic research, so we rarely know what it will end up being used for. Even from the start, we find applications difficult to imagine," says Jacob Holm, who adds:

"the design of microchips and circuit boards, found in all electronics, could be an area where our result ends up being used. When drawing wires on a circuit board, they must never intersect. Otherwise, short circuits will occur. The same applies to microchips, which contain millions of transistors and for which one must have a graph drawing."