The Taub Faculty of Computer Science Events and Talks

The problem of finding the minimum s-t cut between a source s and a sink t in a graph is a well-studied problem in computer science. Finding the minimum s-t cut in a planar graph has applications in many fields - from traffic design to computer vision.

The geometrical duality between a minimum s-t cut in an undirected planar graph and cycle on the plane that separates t from s was first used by Itai and Shiloach to solve the minimum cut problem, and more efficient algorithms for the problem using the same approach followed.

We use this approach to show an algorithm that finds the minimum s-t cut in an n-vertices undirected planar graph in O(n log log n) time. We then use the improved minimum cut algorithm to solve related problems, including the maximum flow problem in undirected planar graphs, within the same time bound.

Using a similar technique we obtain a dynamic data structure that allows edge capacity changes and answers minimum cut queries between any pair of vertices in O(n^(2/3) polylog(n)) time for undirected planar graphs.

Joint work with Giuseppe F. Italiano, Piotr Sankowski, and Christian Wulff-Nilsen