January 3rd, Tuesday 12:00, Room 506, Jacobs Building

Title: Exploiting Graph Structure - Beauty and Efficiency in Planar Graphs

Lecturer: Shay Mozes

Lecturer homepage : http://www.cs.brown.edu/~shay/

Affiliation : Computer Science department, Brown University

In algorithmic graph theory one strives to exploit graph structure to design efficient algorithms for important, practical problems. In this talk we make the case for this paradigm by discussing recent progress in algorithms for fundamental optimization problems in planar graphs, with applications to basic problems in computer vision known as early vision tasks. We first discuss nearly linear time algorithms for computing shortest paths in directed planar graphs with positive and negative length arcs. We then describe in more detail a nearly linear time algorithm for finding a maximum single commodity flow in a planar network with multiple sources and sinks. These algorithms rely on a host of structural properties of planar graphs, including a beautiful relation between circulations in a planar graph and shortest paths in the planar dual of that graph. We conclude with a brief discussion of distance oracles for planar graphs. No prior knowledge of planar graphs is assumed.