The Tragedy of Being Almost but Not Quite Planar (Invited Talk)

Author Jeff Erickson



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.2.pdf
  • Filesize: 326 kB
  • 1 pages

Document Identifiers

Author Details

Jeff Erickson
  • University of Illinois Urbana-Champaign, IL, USA

Cite AsGet BibTex

Jeff Erickson. The Tragedy of Being Almost but Not Quite Planar (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.2

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Computational geometry
Keywords
  • planar graphs
  • surface graphs
  • algorithms
  • open problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail