Seminar on Algorithms for Planar Graphs (0368-4618-01) Fall 09/10

Haim Kaplan

We will cover few fundamental algorithms for planar graphs.

Tentative schedule

1)        Efficient planarity testing by Hopcroft and Tarjan 

        Journal of the ACM 21(4) 1974

        Presentation by Guy Wertheim (3/11/2009)


      2)         A separator theorem for planar graphs by Lipton and Tarjan

        SIAM J. Appl. Math. 36, 177-189, 1979

        Presentation by Sarel Cohen (10/11/2009)


      3)         Faster Shortest-Path Algorithms for Planar Graphs by Henzinger, Klein, Rao, and Subramanian

         J. Comput. Syst. Sci. 55(1): 3-23, 1997

         Presentation by Esther Khaitsun (17/11/2009)


4)        Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(n log2 n)-Time Algorithm by Klein, Mozes, and Weiman

        Symposium on Discrete Algorithms, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, 236-245, 2009

         Presentation by Inon Peled (pdf) (24/11/2009)


5)         Maximum Flow in Planar Networks by Itai and Shiloach

         SIAM J. Comput. 8(2): 135-150, 1979



6)         An O(n log˛ n) Algorithm for Maximum Flow in Undirected Planar Networks by Hassin and Johnson

         SIAM J. Comput. 14(3): 612-624, 1985

         Presentation by David Levit Gurevich (15/12/2009)


      7)         The Lattice Structure of Flow in Planar Graphs by Kuller, Naor, and Klein

         SIAM J. Discrete Math. 6(3): 477-490, 1993


8)         An O(n log n) algorithm for maximum st-flow in a directed planar graph by Borradaile and Klein

         J. ACM 56(2), 2009

         Maximum Flows and Parametric Shortest Paths by Erickson   

         Presentation by Eran Nir and Matan Laadan (22/12/2009)


9)        An O(n log n) approximation scheme for Steiner tree in planar graphs by Borradaile, Klein, and Mathieu

        ACM Transactions on Algorithms 5(3): 2009

        Presentation by Shai Hertz (29/12/2009)


Anyone who joins the seminar later (i.e. did not attend the first meeting) or drops off please send me email


There will be no meeting today 27/11. Our first lecture would be on the 3/11