Planar graphs arise in applications such as road map navigation and logistics, graph drawing, and image processing. Our focus will be on recent research results for classical problems that exploit planarity, for example: Traveling Salesperson, Shortest Paths, Multicommodity Flow, and Maximum Flow. We will also cover the data structures that are used by these algorithms, for example: Dynamic Trees.

This class will emphasize using the structure of a problem to design the best (fastest and simplest) algorithm to get the job done.

Prerequisite: CS 157 or equivalent
(introductory algorithms).

Lectures and homeworks

News: