2026-07-22T15:59:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17287 2024-03-06T10:59:22Z ddc:004 open_access

The Tragedy of Being Almost but Not Quite Planar (Invited Talk) Erickson, Jeff planar graphs surface graphs algorithms open problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff Erickson 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.2 urn:nbn:de:0030-drops-172875 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.2 eng https://creativecommons.org/licenses/by/4.0/legalcode