The Operations Research & Statistics seminar
Date: April 29, 2013
Speaker: Yahav Nussbaum from TAU
Title: Maximum Flow in Planar Graphs
Time and place: 12:30 in Bloomfield-527
A graph is planar if it can be embedded in the plane such that no two edges
intersect. Planar graphs appear in many applications, such as road transportation,
VLSI design, computer vision, and others. The rich combinatorial
structure of planar graphs allows us to find efficient algorithms for classical
combinatorial problems in this kind of graphs, that have better time bounds
than algorithms for general graphs.
In this talk I will describe planarity-exploiting algorithms for some versions
of the maximum flow problem in planar graphs. Our results are based on
two main tools. The first is the associated dual graph, which exists for every
planar graph. The second is a divide-and-conquer approach based on planar
graphs separators.
The talk is based on a joint work with Glencora Borradaile, Philip N. Klein,
Jakub Lacki, Shay Mozes, Piotr Sankowski and Christian Wulff-Nilsen
You can watch the rest of the seminar plan at our web site
Or-seminar mailing list
Statseminar mailing list
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>