All about Planar Graphs

COSC 149.12, Fall 2024

Main | Schedule | Homeworks | About

About the course

Planar graphs are among the most well-studied graph classes since the beginning of graph theory and algorithm design. Planar graphs can manifest in computational problems as networks, meshes, or terrains that are geometric and low-dimension in nature, which unsurprisingly find many applications in computer graphics, visualization, vehicle routing, and shape analysis. This graduate-level seminar-style course is aimed to introduce a vast array of tools for planar graphs, ranging from combinatorial to geometric to spectral to algorithmic and beyond. Naturally, due to the sheer amount of work and literature in the area, the topics covered in this class will be biased towards the interest and expertise of the instructor.

Course Objectives

The course serves as an opportunity for people interested in planar graphs and their applications to learn about the various tools and techniques developped, both classical and recent.

Prerequisite

Students are assumed to have the math maturity to read and write proofs and establish basic properties of newly encountered mathematical structures. Knowledge in graph theory (COSC 30 Discrete Math or Math 38 Graph Theory) and linear algebra (Math 22, Math 24 or COSC 70 or Instructor Permission) are required as prerequisite. Knowledge in algorithms (COSC 31 Algorithms) are strongly recommended.

Teaching Methods and Expectations

The class will mostly be lecture-based in a seminar style. Every lecture will be given by one of the students, presenting important ideas extracted from the reference papers after discussing with the instructor. Another student will be assigned to scribe for the lecture. After the class, the presenter and the scribe are responsible to produce the lecture notes. We will occasionally have homework problems to complement the lectures. Every student is expected to finish the reading assignment before the class, taking notes and contributing to discussion during the class, and solidify the understanding of the material by solving the homework problems. We will assign roles to each student (technician, historian, architect, etc.) so that you may pay attention to part of the material during the paper reading and provide help and comments during the lecture. And we will use the presentation, scribe notes and homework submissions to determine if the students are actively engaging in learning.

Textbook and References

There is no required textbooks. The class touches upon various topics in combinatorial topology, graph minor theory, topological graph theory, graph drawing, spectral graph theory, and graph algorithms; many topics are based on currect active research in the field. As a result, there isn’t any single textbook or lecture note that covers all the materials we will be talking about. (In fact, the instructor is hoping to write high-quality lecture notes that can be used by future students and researchers.) Relevant reading materials will be linked on the course webpage each week; the instructor can provide additional references upon request.

Here is a list of books and lecture notes on computational topology. Not all of them are relevant to this course, but I find them helpful in my study.

Jean-Daniel Boissonnat and Monique Teillaud, Effective Computational Geometry for Curves and Surfaces
Éric Colin de Verdière, Algorithms for Embedded Graphs
Robert Ghrist, Elementary Applied Topology
Philip Klein and Shay Mozes, Optimization Algorithms for Planar Graphs
Dmitry Kozlov, Combinatorial Algebraic Topology
Francis Lazarus and Arnaud de Mesmay, Computational Topology: Lecture notes
Laszlo Lovasz, Graphs and Geometry
Jiří Matoušek, Using the Borsuk-Ulam Theorem
Jaroslav Nesetril, Patrice Ossona de Mendez, Sparsity
John Stillwell, Classical Topology and Combinatorial Group Theory

Related Courses

Here is a list of related courses offered by other instructors. Most of these courses are focusing on a specific aspect of planar graphs (and goes much deeper). My hope is to provide an overview of all the important tools on planar graphs.

Discrete Differential Geometry: An Applied Introduction by Keenan Crane
Algorithms for Planar Graphs and Beyond by Erik Demaine, Shay Mozes, Christian Sommer, and Siamak Tazari
One-Dimensional Computational Topology by Jeff Erickson
Topological Graph Theory by Jeff Hicks
Optimization Algorithms for Planar Graphs by Philip Klein
Algorithms for Planar Graphs by Shay Mozes
Graph Minor Theory by Sergey Norin
Sparsity by Marcin Pilipczuk and Michał Pilipczuk

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible, or before the end of the second week of the term—at the latest, to discuss appropriate adjustments.

Accessibility Services

Students requesting disability-related accommodations and services for this course are encouraged to schedule a meeting with me as early in the term as possible. This conversation will help to establish how your accommodations will be implemented in my course and what role Student Accessibility Services (SAS) or its Testing Center may play in assisting. In order for accommodations to be authorized, students are required to register with SAS (Getting Started with SAS webpage; student.accessibility.services@dartmouth.edu; 603-646-9900) and to request an accommodation email be sent to me in advance of the need for an accommodation. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

last modified on