The Taub Faculty of Computer Science Events and Talks

Graph optimization problems are the most studied problems in theoretical computer science. These problems are not only mathematically intriguing. They have a crucial impact on our increasingly-computerized environment. Among the tractable optimization problems, the most fundamental are shortest paths, maximum flow, minimum cut, maximum matching, and minimum spanning tree. On planar graphs, these problems are all inter-related through fascinating connections. By exploiting these connections, and the remarkable wealth of structural properties exhibited by planar graphs, these problems can all be solved on planar graphs faster than on general graphs.

Research on planar graphs today is in an auspicious position where theoretical and practical goals are well aligned. On the theoretical side, research on planar graphs has produced over the last few years a variety of surprising and deep new ideas and techniques. On the practical side, planar graphs are useful for modeling real-world scenarios such as road networks, VLSI layouts, medical imagery, and satellite imagery. Presently there is a growing need for faster algorithms, driven by a dramatic increase in both the number of instances and their sizes. For example, GPS navigation and image processing induce planar graph optimization problems and are ever-more popular in a world with more than a billion smartphones.

In the talk, I will give a high level overview on the connections between shortest paths and various other optimization problems in planar graphs. In particular, I will show how many classical optimization problems can be solved on planar graphs in nearly linear time.

Bio:
Oren is a faculty member in the Computer Science department at the University of Haifa. He received his Ph.D. in 2009 from the Massachusetts Institute of Technology under the guidance of Prof. Erik Demaine. Oren's research is about the design and analysis of algorithms and data structures for combinatorial optimization problems. Mostly, Oren is interested in optimization problems arising in pattern matching and in planar graphs and involving shortest paths.

The talk will be based on a graduate course on planar graphs that Oren teaches regularly at the University of Haifa.