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
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