If we draw such graphs, we can change computers forever.
Jacob Holm, Associate Professor of Computer Science at the University of Copenhagen, reviewed evidence from scientific articlepublished on the Internet in October 2019 by him and his colleague Eva Rotenberg (Associate Professor of the Department of Applied Mathematics and Computer Science at the Danish Technical University), and found that their results unwittingly gave a solution to the centuries-old graph problems.
Holm was glad no one had found a solution before. “It was just the right moment to shout Eureka,” he said, “suddenly it seemed obvious.”
Holm and Rothenberg tried to find an optimal way to determine whether a graph is “flat”, that is, whether it can be drawn flat on a surface without intersecting lines (flat graph drawings are also called “nesting”).
To put it very bluntly, we have formally defined why a certain typeface is awful.
In the minds of mathematicians, the graph is often different from what most of us were taught in school. The graph in this case is any number of points called nodes connected by pairwise connections called edges. In other words, an edge is a curve that connects two nodes. According to this definition, a graph can represent everything from complex wiring inside computer chip to a city roadmap, where the streets of Manhattan can be represented as edges and their intersections as nodes. Graphs are studied in graph theory.
Engineers need to find planarity in a graph when, for example, they design a computer chip without crossing wires. However, it is difficult to assess the planarity when adding and removing edges without drawing the graph yourself and trying to avoid crossing the lines (see “The” Cottages and Wells “problem” below, which was first published in the issue The Strand Magazine in 1913).
Estimating planarity becomes even more difficult in large graphs with a large number of nodes and edges, Rothenberg says. This is not an abstract problem. Quantum computer chipsfor example, advanced devices, and finding effective ways to assess their planarity without wasting time and money is critical to their development.
Each of the three houses needs access to water, gas and electricity, but for safety reasons, the lines connecting utilities and houses cannot cross. Take a piece of paper, draw this problem, and try to connect all three houses to all three utilities so that the lines don’t cross. If you think you got the right answer, check it out at the bottom of this page.
In the original 2019 article published on the preprint server arXivWhere research is often first published before peer review, Holm and Rotenberg have classified the type of investment as “balanced” or “good” investment.
Holm explains that these good investments “tend to” balance ” [временные] the cost of edge insertion, so no possible edge insertion is too expensive compared to the rest. ” This concept is borrowed from balanced decision trees in computer science, which are designed with equally spaced branches to minimize search time. In other words, it is easier to add new edges to good nesting without breaking the planarity.
“If you look at it,” says Holm, “a good investment is simple, straightforward. A common example is the so-called ladder graph. A balanced nesting of this graph looks exactly like a ladder. ” However, Holm said the following: “In an unbalanced investment, it is difficult to recognize.”
From a subjective point of view, a ladder graph is “good” and its alternatives are “bad,” but Holm and Rotenberg articulate in their paper why these statements are mathematically correct. “To put it very bluntly, we formally defined why a certain typeface is awful,” says Rotenberg, referring to a poor investment. At the time, both scientists did not realize that their good investment class played a significant role in speeding up the dynamic planarity testing process.
When you need to add a new edge to a planar graph, two scenarios are possible: there is a way to safely add an edge, perhaps after changing the face, or there is no face that allows a new edge. However, in some cases, nesting the graph itself may obscure the planar edge insertion method. To identify such alternative ways, mathematicians “flip” the attachment, changing its orientation while maintaining its mathematical identity, since the connections between the connected nodes and edges did not change.
Such flips can allow the addition of edges between two newly ordered nodes that would otherwise violate planarity. Holm and Rothenberg found that coups that lead to successful insertion and removal of edges tend to fall into their class of so-called good nesting. Likewise, these good nestings require fewer flips to successfully add new edges. A win-win.
Scientists have proposed many applications for their work, including chip design, surface grids and road networks, but Rotenberg admitted, “What attracts us to this problem is its mysterious nature.” Scientists are wary of predicting more commercial applications because flipping real-world graph designs can be challenging.
However, they believe that their approach to evaluating dynamic graphs (that is, graphs that change through insertions and deletions) may influence the way mathematicians approach similar problems. Basically, by evaluating planarity, their algorithm also tracks and computes changes in the graphs, doing what’s called “regression analysis,” says Rothenberg.
Collecting even this kind of data is not overkill. According to Rotenberg, their solution shows that regression analysis can have algorithmic applications, in addition to being “interesting in itself,” because here it led to an efficient planarity test.
Analyzing dynamic mathematical concepts is an “open field,” she says, but has potential. Such breakthroughs may have already taken place – they are simply hidden in the process.
Solution of the problem “Houses and wells”: in fact, this problem cannot be solved in two-dimensional space.
Find out the detailshow to get Level Up in skills and salary or a profession in demand from scratch. Discount only for habravchan residents 50% with a promo code HABR…
Other professions and courses
PROFESSION
COURSES
Similar Posts
