Popular Mechanics (South Africa)
If we draw graphs like this, we can change computers
JACOB HOLM WAS FLIPPING THROUGH proofs from an October 2019 research paper he and colleague Eva Rotenberg – an associate professor in the department of applied mathematics and computer science at the Technical University of Denmark – had 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 ‘planar’ – that is, if it could be drawn flat on a surface without any of its lines crossing eachother(flatdrawingsofagrapharealsocalled‘embeddings’).
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. You can experience this precise challenge with a brain teaser called ‘The Three Utilities Problem’, published in an issue of The Strand Magazine in 1913 (see sidebar).
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.
In their original 2019 paper published on the preprint server arXiv – where research often first sees the light of day before peer review – Holm 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 minimised 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 recognisable.’
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 didn’t realise 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 hasn’t 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.
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 (that is to say, 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 isn’t 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.
Analysing dynamic mathematical concepts is an ‘open field,’ she says, but therein lies the potential. The breakthroughs might have already happened – they’re just hidden in the process.