The Tragedy of Being Almost but Not Quite Planar (ISAAC 2022)
Channel: Jeff Erickson
Date: 2022-12-19

Invited talk "at" the 33rd International Symposium on Algorithms and Computation (ISAAC 2022).

Abstract: Planar graphs have been fertile grounds for algorithms research for decades, both because they model several types of real-world networks, and because they admit simpler and and faster algorithms than arbitrary graphs. Many important structural properties of planar graphs extend naturally to graphs that embed on more complex surfaces. As a result, efficient algorithms for planar graphs often extend naturally to higher-genus surface graphs with little or no modification. I will describe a few of my favorite exceptions to this rule—classical problems that admit simple, efficient, and practical algorithms for planar graphs, but where algorithms for graphs on other surfaces are significantly slower and/or more complex.