北京雁栖湖应用数学研究院

Planar graphs form one of the most fundamental classes of graphs in both theory and applications. This course provides an introduction to planar graphs with an emphasis on algorithmic and complexity-theoretic perspectives. We will cover foundations: embeddings, planarity testing, duality, Euler’s formula, flows, matchings, and the planar separator theorem. We will study classical algorithms tailored to planar graphs, such as linear-time planarity tests, shortest paths, and perfect matchings. We also explore the complexity landscape of planar problems, including Planar 3-SAT and planar variants of NP-hard problems, as well as consequences of the Robertson–Seymour graph minor theorem.