Post #457

If We Draw Graphs Like This, We Can Change Computers Forever The title is catchy, but the article is "only" about improvement for dynamic planarity testing problem. Planarity testing is well-studied problem for testing if a graph can be drawn without crossing edges and O(n) algorithms are known. This article on the other hand studies the case when the edges may be added and removed and the question is how to redraw the graph so that it becomes planar. The results were published at STOC'20.