Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs
event speaker icon
Yahav Nussbaum (Tel-Aviv University)
event date icon
Wednesday, 02.03.2011, 12:30
event location icon
Taub 701
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