Algorithmic and Complexity Aspects of Planar Graphs
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.
Lecturer
Date
22nd September ~ 15th December, 2025
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Monday | 13:30 - 16:55 | A3-3-201 | ZOOM 01 | 928 682 9093 | BIMSA |
Prerequisite
None.
Syllabus
TBD
Audience
Advanced Undergraduate
, Graduate
Video Public
No
Notes Public
No
Language
Chinese
Lecturer Intro
Hanru Jiang obtained a Ph.D. in computer science and technology from the University of Science and Technology of China in 2019. From 2019 to 2020, he worked as an assistant research fellow at the Quantum Computing Research Center of Pengcheng Laboratory. In 2020, he joined BIMSA as an assistant professor. His main research directions are programming language theory, compiler verification, and programming language aspects in quantum computing. As the main contributor to the concurrent program separation compilation verification work CASCompCert, won the Distinguished Paper Award of PLDI 2019, a top conference in the field of programming languages.