New Algorithm for Graph Crossings
Primary resource consulted: https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/
A summary:
The article linked explores the journey of two scientists, Jacob Holm and Eva Rotenberg, who were looking for the key needed to formulate a faster algorithm that could determine when adding edges to a graph is possible so that the resulting graph remains “planar.” This more efficient algorithm would improve upon one that was published a couple decades ago. “Planar” here means the graph has edges that do not cross each other. It is difficult to tell whether or not a graph is planar the more complicated it is! And this was the problem: how can we quickly tell whether a potential change to the graph will still allow it to be planar? The old algorithm checked planarity at a rate of steps that was about the square root of the number of nodes in the graph. In Big O Notation, that’s O(sqrt(n)). The new algorithm checks planarity at a rate proportional to the cube of the logarithm of nodes in the graph, which in Big O Notation would probably be O(log^3(n)) (or not, I’m not a comp sci major, lol). Below is a visual representation of how many “flips” must be performed if we want to connect nodes 1 and 6 without our new edge (dotted red line) crossing the other established edges (blue lines). The green edge connecting 1 and 6 in the 3rd image obviously maintains planarity of the graph.
Holm and Rotenberg were able to figure out how to decrease the number of “flips” needed to accomodate a new edge from one of their previously published papers. The resulting insertion algorithm was relatively simple…and much faster. This one only performs the changes necessary to insert the new edge. No superfluous flipping here!
How it’s relevant:
This article directly connects to the 2040 course material considering it’s all about graphs + their nodes and edges! What I appreciate most about the article is that it introduced a “new” (well, new to me at least) component of graphs: planarity. In the first two weeks of class we covered other components of graphs: nodes, edges, paths, path length, weak/strong ties, etc., but not planarity (or perhaps Prof. Easley mentioned it in lecture but I didn’t recall, lol)! What’s interesting is that when I was doing the first problem set and had to draw a graph (nodes + edges + labelling) from the description given, I instinctively drew it so that none of the edges intersected. I don’t like the look and feel of edges that crash into one another. It lessens the overall, ahem, jenny say quan of the graph. *crickets* Little did I know that this is an actual property of graphs depicting networks! I was maintaining planarity before I knew what it was! I also appreciate the article’s discussion of algorithms and runtime. Overall a really great article and applicable to what we’ve learned thus far!