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

Date:
August 17, 2020
Source:
University of Copenhagen
Summary:
Researchers thought that they were five years away from solving
a math riddle from the 1980's. In reality, and without knowing,
they had nearly cracked the problem and had just given away much
of the solution in a research article. The solution could be used
to improve tomorrow's phones and computers.



FULL STORY ========================================================================== COMPUTER SCIENCE Researchers from the University of Copenhagen and the Technical University of Denmark (DTU) thought that they were five years
away from solving a math riddle from the 1980's. In reality, and without knowing, they had nearly cracked the problem and had just given away
much of the solution in a research article. The solution could be used
to improve tomorrow's phones and 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.

Read the research article: https://arxiv.org/abs/1911.03449 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."
###

========================================================================== Story Source: Materials provided by University_of_Copenhagen. Note:
Content may be edited for style and length.


==========================================================================


Link to news story: https://www.sciencedaily.com/releases/2020/08/200817123034.htm

--- up 4 weeks, 5 days, 1 hour, 55 minutes
* Origin: -=> Castle Rock BBS <=- Now Husky HPT Powered! (1337:3/111)