Topic: vertices

Maria Chudnovsky introduces graph theory through relationships represented as vertices and edges. She discusses the perfect graph problem, practical uses of abstract structure and her path into mathematics, including an application to wedding seating, in conversation with Janna Levin.

Monika Henzinger surveys algorithms that maintain graph information as vertices and edges change. The lecture explains major algorithmic techniques and open problems, and shows how dynamic data structures support applications such as clustering and recent breakthroughs in static maximum-flow and minimum-cost-flow algorithms.