Mediaboss Marketing

Jacob Holm was flipping through proofs from an October 2019 research paper he and colleague Eva Rotenbergan associate professor in the department of applied mathematics and computer science at the Technical University of Denmarkhad published online, when he discovered their findings had unwittingly given away a solution to a centuries-old graph problem.

Holm, an assistant professor of computer science at the University of Copenhagen, was relieved no one had caught the solution first. It was a real Eureka! moment, he says. It suddenly seemed obvious.

Holm and Rotenberg were trying to find a shortcut for determining whether a graph is planarthat is, if it could be drawn flat on a surface without any of its lines crossing each other (flat drawings of a graph are also called embeddings).

Putting it very bluntly, we formally quantified why something is a terrible drawing.

To mathematicians, a graph often looks different than what most of us are taught in school. A graph in this case is any number of points, called nodes, connected by pairwise relations, called edges. In other words, an edge is a curve that connects two nodes. Under this definition, a graph can represent anything from the complex wiring inside a computer chip to a road map of a city, in which the streets of Manhattan could be represented as edges, and their intersections represented as nodes. The study of such graphs is called graph theory.

Engineers need to find planarity in a graph when, for example, they are designing a computer chip without a crossed wire. But assessing for planarity amid the addition and removal of edges is difficult without drawing the graph yourself and trying not to cross any lines (See The Three Utilities Problem below, which was originally published in an issue of The Strand Magazine in 1913).

This content is imported from {embed-name}. You may be able to find the same content in another format, or you may be able to find more information, at their web site.

Assessing for planarity becomes even more complicated in larger graphs with lots of nodes and edges, says Rotenberg. This is a real-world issue. Quantum computer chips, for instance, are highly advanced, and finding efficient ways to assess their planarity without wasting time and money is crucial to their development.

These three houses each need access to water, gas, and electricitybut for safety reasons the lines connecting the utilities and houses cannot cross. Grab a sheet of paper, draw out this scenario, and try to connect all three houses to all three utilities without any two lines crossing. Check the solution at the bottom of this page when you think you have the right answer.

In their original 2019 paper published on the preprint server arXivwhere research often first sees the light of day before peer reviewHolm and Rotenberg classified a type of embedding called a balanced or good embedding.

Holm explains that these good embeddings tend to balance the [time] costs of inserting edges so that no possible edge insertion costs too much compared to the rest. This is a concept borrowed for balanced decision trees in computer science, which are designed with evenly dispersed branches for minimized search time. Put another way, good embeddings are easier to add new edges to without violating planarity.

If you were to look at it, Holm says, a good embedding would be simple, unconvoluted. The standard example is the so-called Ladder Graph. A balanced embedding of this graph looks exactly like a ladder. But Holm says: In an unbalanced embedding, it is hardly recognizable.

It seems subjective to say the Ladder Graph is good and its alternatives are bad, but Holm and Rotenberg articulated in their paper why those statements were mathematically true. Putting it very bluntly, we formally quantified why something is a terrible drawing, says Rotenberg, referring to a bad embedding. What the pair didnt realize at the time was that their class of good embeddings played an essential role in speeding up the process of dynamic planarity testing.

When adding a new edge to a planar graph is required, there are two scenarios: There is a safe way to add the edge, possibly after modifying the drawing, or no drawing admitting the edge exists. But in some cases, the embedding of a graph itself might be disguising a way the edge could be inserted in planar fashion. To reveal those alternative paths, mathematicians flip an embedding to change its orientation while keeping it mathematically identical, because the relationship between the connected nodes and edges hasnt changed.

These flips might make it possible to add edges between two newly arranged nodes, edges that would have otherwise violated planarity. Holm and Rotenberg discovered the flips that lead to successful edge insertion and deletion tended to fall into their class of so-called good embeddings. Similarly, these good embeddings require fewer flips overall to successfully add new edges. A win-win.

Infinite Powers: How Calculus Reveals the Secrets of the Universe

Zero : The Biography of a Dangerous Idea

The Art of Statistics: How to Learn from Data

The Joy of x: A Guided Tour of Math, from One to Infinity

The pair have suggested numerous applications for their work, including chip design, surface meshes, and road networks, but Rotenberg has admitted: What attracts us to this problem is its puzzle-like nature. The two are cautious to predict more commercial applications because completing flips in real-world graph designs can be challenging.

However, they say that their approach to assessing dynamic graphs (i.e., graphs that change via insertions and deletions) could impact how mathematicians approach similar problems. Essentially, while their algorithm assesses planarity, it also tracks and calculates changes to the graphs, performing what is called a recourse analysis, says Rotenberg.

But such data gathering isnt superfluous. Rotenberg argues their solution shows that recourse analysis could have algorithmic applications in addition to being interesting in its own right, because here, it led to their efficient planarity test.

Analyzing dynamic mathematical concepts is an open field, she says, but therein lies the potential. The breakthroughs might have already happenedtheyre just hidden in the process.

Solution to the Three Utilities Problem: Its actually impossible in two-dimensional space.

Editor's Note: This story first appears in the March/April 2021 issue of Popular Mechanics magazine.

This content is created and maintained by a third party, and imported onto this page to help users provide their email addresses. You may be able to find more information about this and similar content at piano.io

Read the original here:
The Three Utilities Problem | Graph Theory Breakthrough - Popular Mechanics