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 ~ 29th 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 is an Associate Researcher at BIMSA. He received his Ph.D. in Computer Science and Technology from the University of Science and Technology of China in 2019. From 2019 to 2020, he was an Assistant Researcher at the Quantum Computing Research Center, Peng Cheng Laboratory. His research interests lie in programming language theory, formal verification of compilers, and programming language issues in quantum computing. His work has been published in premier venues such as PLDI, CAV, and OOPSLA. He was a recipient of the PLDI 2019 Distinguished Paper Award.