CS 762: Graph Theoretic Algorithms, Winter 2011

www.student.cs.uwaterloo.ca/~cs762/

Anna Lubiw, David R. Cheriton School of Computer Science, University of Waterloo
alubiw@uwaterloo.ca, DC 2334, (519) 888-4567, ext. 34449

Contents: Organization, Course Outline, Assignments, Resources, Lectures, Project, Presentation Schedule

Announcements

Sun. Feb. 20. Assignment 2 is available below.
Sat. Feb. 5. Assignment 1, Problem 2 needs some fixes.
Sun. Jan. 30. Two small typos corrected in Assign 1 (shown in red in the pdf).
Mon. Jan. 24. Assignment 1 is available below.
first class is Wednesday January 5.

Organization

Time and Place: MW, 11:00 -- 12:20. MC 2036. Note that we moved to the bigger room next door. (MC 2036 rather than 2036A.)

Credit:

4 assignments (50%)
a project (50%). Pick some topic that interests you and is relevant to the course; explore some aspect of it; read a paper or two; write a report and a make a class presentation. I will suggest possible topics.

Assignments

Assignments will be marked based on correctness but also on quality of explanations: strive for clarity and precision. Assignments are due Mondays in class.

		Due
	Assignment 1 [pdf]	Wed. Feb. 9
	Assignment 2 [pdf]	Wed. March 9
	Assignment 3 [pdf]	Wed. March 30
	Assignment 4 []	we may not have time for a 4th assignment

Course Outline

Topics:

planar graphs: planarity testing, problems that are easier on planar graphs, drawing planar graphs, planar separators.
intersection graphs and related classes: interval and chordal graphs, unit disc graphs, etc.
trees and related graphs: treewidth, series parallel graphs, problems that are easier on these, intro to graph minors.

Background: I will assume a background in algorithms and data structures equivalent to a decent undergraduate course (e.g. UW's CS 341), and some graph theory.

Resources

CS 762 course notes by Therese Biedl. You will get the password in class. Professor Biedl would like these notes kept private, so please do not make them publically available.
Wikipedia Book: Graph Algorithms

Finding Papers

Lectures

Numbers in square brackets refer to the course notes.

Lecture 1, Wed. Jan. 5: Intro

introduction to graph algorithms
beginning planar graphs: definitions [section 11.1], Euler's formula [section 11.4], combinatorial planar embeddings [section 11.1], Whitney's Theorem [section 11.1].

Lecture 2, Mon. Jan. 10: Planar graphs and Triangulations

number of edges <= 3n-6 [section 11.4]
triangulations are 3-connected [section 16.1]
how to augment a planar graph to a triangulation in linear time [section 16.2]
dual planar graph [section 11.2]
mention of Kuratowski's theorem

Lecture 3, Wed. Jan. 12: Testing Planarity in Linear Time

the version I'm presenting is outlined in Haeupler and Tarjan, Planarity Algorithms via PQ-Trees
also see the course notes [chapter 15]

Lecture 4, Mon. Jan. 17: Straight-Line Planar Drawing

I presented Schnyder's method. A concise exposition is here.

Lecture 5, Wed. Jan. 19: Some Easy and Hard Problems on Planar Graphs

I covered the material of [chapter 12] (except I did isomorphism instead of 2-path).

Lecture 6, Mon. Jan. 24: Max Flow in Planar Graphs

from [chapter 14] of the course notes. Plus some material on Menger's theorems [section B.2.3], and disjoint paths.

Lecture 7, Wed. Jan. 26: Planar Separator Theorem

see [chapter 18], but note that it assumes knowledge and results on tree-width which we have not covered yet.
separators in trees
proof of the planar separator theorem due to Alon, Seymour, Thomas (see wikipedia for an outline, or see section 1 of their paper)

Lecture 8, Mon. Jan. 31: Algorithms using Planar Separators, Baker's Method

divide and conquer example: a faster exact algorithm for independent set on planar graphs
approximation algorithms for independent set on planar graphs using planar separators, and using Baker's method [section 17.3.4]

Lecture 9, Wed. Feb. 2: Other Representations of Planar Graphs

presentation by Soroush Alamdari. Schnyder Greedy Routing Algorithm, He, Zhang, TAMC 2010, link
Steinitz's theorem, circle packing
visibility representation [section 16.4.2]

Lecture 10, Mon. Feb. 7: Interval Graphs

interval graphs: recognition, optimization, perfect elimination orders [chapter 2]
I will mention perfect graphs. In addition to the references in the course notes, you can read about the perfect theorem here.

Lecture 11, Wed. Feb. 9: Chordal Graphs

[chapter 3]

Note: there will be no classes for the following 2 weeks (I'll be away for one week, and then there's reading week).

Lecture 12, Mon. Feb. 28: Comparability Graphs

[chapter 4]

Lecture 13, Wed. March 2: Permutation Graphs

presentation by F. Barrera Cruz. [Schnyder embeddings for non-triangulated graphs] in "Geometric Graphs and Arrangements", Felsner, 2004, link, or in the library, or ask to borrow my copy.
presentation by Thang Le. Beyond the flow decomposition barrier, Goldberg, Rao, JACM 1998, link
permutation graphs

Lecture 14, Mon. March 7: Other Geometric Graphs

string graphs
contact graphs
visibility graphs
these topics are not covered in the course notes, but the wikipedia pages are a good start

Lecture 15, Wed. March 9: Treewidth

[sections 7.2, 7.3]

Lecture 16, Mon. March 14:

presentation by T. Wang. Linear-time transitive orientation, McConnell, Spinrad, SODA 1997. link
presentation by A. Tsang. Contact representations of planar graphs with cubes, Felsner, Francis. link
max ind. set in graphs of bounded treewidth [section 9.2]

Lecture 17, Wed. March 16:

presentation by L. Inozemtseva. New Linear-Time Algorithms for Edge-Coloring Planar Graphs, Cole and Kowalik, Algorithmica 2008. link
presentation by W. Yu. Reconstructing a simple polygon from its angles, Disser, Mihalak, Widmayer, SWAT 2010. link
other problems on graphs of bounded treewidth, Courcelle's theorem [section 9.2.5]

Lecture 18, Mon. March 21:

presentation by Z. Li. Dominator tree verification and vertex-disjoint paths. Georgiadis and Tarjan, SODA 2005. link
separators in graphs of treewidth k [section 18.4]
recognition of graphs of treewidth k [section 9.3 and 18.6] For more information, see: Treewidth and computations I. Upper bounds, Bodlaender and Koster, Information and Computation 2010. link

Lecture 19, Wed. March 23:

presentation by B. Li. Treewidth and pathwidth of permutation graphs, Bodleander, Klols, Kratsch, SIAM J. Disc. Math, 1995.199 link
presentation by B. Wilkinson. Map graphs, Chen, Grigni, Papadimitriou, JACM 2002, link

Lecture 20, Mon. March 28:

presentation by S. Rahbar. On Coloring Unit Disc Graphs, Graf, Stumpf, Weisenfels, Algorithmica 1998. link.
presentation by N. Zhang. Exact Shortest Path Queries for Planar Graphs Using Linear Space. Mozes, Sommer, 2010. link

Lecture 21, Wed. March 30:

presentation by A. Mehrabian. The Bidimensionality Theory and Its Algorithmic Applications, Demaine and Hajiaghayi, The Computer Journal, 2008, link
presentation by N. Shkrob. Improved dynamic reachability algorithms for directed graphs, Roditty and Zwick, 2002 link and Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components, Lacki, SODA 2011 link

Lecture 22, Mon. April 4:

presentation by S. Pidcock. Linkless and flat embeddings in 3-space and the unknot problem, Kawarabayashi, Kreutzer, Mohar, SoCG 2010. link

Here are some possible project topics. You must write a report (about 5 pages) and do a class presentation (20 minutes, including some time for questions). The goal of the presentation is to tell the class what is in the paper. I encourage presentations early in the term. Your written report (due at the end of term) should include:

a brief summary of the paper (in your own words)
your assessment of the contribution (are there new ideas? incremental progress? a solution to an open problem? faster algorithms? practical algorithms?)
your assessment of the presentation (is the paper well organized? is there intuition and rigour? is the paper well-written?)

Some possible papers are as follows. Let me know if you would like to reserve one. You are also welcome to choose papers and topics not on this list. For example, look at the references in the course notes.

Testing planarity of partially embedded graphs, Angelini, Di Battista, Frati, Jelinek, Kratochvil, Patrignani, Rutter, SODA 2010 link
Testing simultaneous planarity when the common graph is 2-connected, Haeupler, Jampani, Lubiw, ISAAC 2010 link
On Triangulating Planar Graphs under the Four-Connectivity Constraint, Biedl, Kant, Kaufmann, link
Finding topological subgraphs is fixed-parameter tractable, Grohe, Kawarabayashi, Marx, Wollan, arXiv 2010, link
Faster shortest-path algorithms for planar graphs, Henzinger, Klein, Rao, Subramanian, JCSS '97, link
A linear-time approximation scheme for planar weighted TSP, Klein, FOCS 2005. link
The LBFS Structure and Recognition of Interval Graphs, Corneil, Olariu, Stewart, SIAM J. Discrete Math 2009. link
Every planar graph is the intersection graph of segments in the plane, Chalopin, Goncalves, STOC 2009.
[bipartite planar graphs as intersection of line segments] On grid intersection graphs, Hartman, Newman, Ziv, Discrete Math. 1991. link
Triangle contact representations and duality, Goncalves, Leveque, Pinlou, Gaph Drawing 2010. link
Triangle-free planar graphs as segment intersection graphs, de Castro, Cobos, Dana, JGAA 2002. link
Computing the Independence Number of Intersection Graphs, Fox and Pach, SODA 2011, link
Unit Rectangle Visibility Graphs, Dean, Ellis-Monaghan, Hamilton, Pangborn, Combinatorics 2008. link
Graph searching, and a minimax theorem for tree-width, Seymour and Thomas, JCT B 1993. link

Reserved papers:

[reserved by S. Alamdari] Schnyder Greedy Routing Algorithm, He, Zhang, TAMC 2010 link.
[reserved by F. Barrera Cruz] [Schnyder embeddings for non-triangulated graphs] in "Geometric Graphs and Arrangements", Felsner, 2004, link, or in the library, or ask to borrow my copy.
[reserved by T. Le] [a paper on max flow] Beyond the flow decomposition barrier, Goldberg, Rao, JACM 1998, link
[reserved by A. Mehrabian] The Bidimensionality Theory and Its Algorithmic Applications, Demaine and Hajiaghayi, The Computer Journal, 2008, link
[reserved by N. Shkrob] Improved dynamic reachability algorithms for directed graphs, Roditty and Zwick, 2002 link and Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components, Lacki, SODA 2011 link
[reserved by B. Wilkinson] Map graphs, Chen, Grigni, Papadimitriou, JACM 2002, link
[reserved by L. Inozemtseva] New Linear-Time Algorithms for Edge-Coloring Planar Graphs, Cole and Kowalik, Algorithmica 2008. link
[reserved by T. Wang] Linear-time transitive orientation, McConnell, Spinrad, SODA 1997. link
[reserved by W. Yu] Reconstructing a simple polygon from its angles, Disser, Mihalak, Widmayer, SWAT 2010. link
[reserved by A. Tsang] Contact representations of planar graphs with cubes, Felsner, Francis. link
[reserved by S. Pidcock] Linkless and flat embeddings in 3-space and the unknot problem, Kawarabayashi, Kreutzer, Mohar, SoCG 2010. link
[reserved by Z. Li] Dominator tree verification and vertex-disjoint paths. Georgiadis and Tarjan, SODA 2005. link
[reserved by B. Li] Treewidth and pathwidth of permutation graphs, Bodleander, Klols, Kratsch, SIAM J. Disc. Math, 1995.199 link
[reserved by S. Rahbar] On Coloring Unit Disc Graphs, Graf, Stumpf, Weisenfels, Algorithmica 1998. link

Presentation Schedule

Wed. Feb. 2. Soroush Alamdari. Schnyder Greedy Routing Algorithm, He, Zhang , TAMC 2010, link
Wed. March 2. F. Barrera Cruz. [Schnyder embeddings for non-triangulated graphs] in "Geometric Graphs and Arrangements", Felsner, 2004, link, or in the library, or ask to borrow my copy.
Wed. March 2. Thang Le. Beyond the flow decomposition barrier, Goldberg, Rao, JACM 1998, link
Mon. March 14. T. Wang. Linear-time transitive orientation, McConnell, Spinrad, SODA 1997. link
Mon. March 14. A. Tsang. Contact representations of planar graphs with cubes, Felsner, Francis. link
Wed. March 16. L. Inozemtseva. New Linear-Time Algorithms for Edge-Coloring Planar Graphs, Cole and Kowalik, Algorithmica 2008. link
Wed. March 16. W. Yu. Reconstructing a simple polygon from its angles, Disser, Mihalak, Widmayer, SWAT 2010. link
Mon. March 21. Z. Li. Dominator tree verification and vertex-disjoint paths. Georgiadis and Tarjan, SODA 2005. link
Wed. March 23. B. Li. Treewidth and pathwidth of permutation graphs, Bodleander, Klols, Kratsch, SIAM J. Disc. Math, 1995.199 link
Wed. March 23. B. Wilkinson. Map graphs, Chen, Grigni, Papadimitriou, JACM 2002, link
Mon. March 28. S. Rahbar. On Coloring Unit Disc Graphs, Graf, Stumpf, Weisenfels, Algorithmica 1998. link.
Mon. March 28. N. Zhang. Exact Shortest Path Queries for Planar Graphs Using Linear Space. Mozes, Sommer, 2010. link
Wed. March 30. A. Mehrabian. The Bidimensionality Theory and Its Algorithmic Applications, Demaine and Hajiaghayi, The Computer Journal, 2008, link
Wed. March 30. N. Shkrob. Improved dynamic reachability algorithms for directed graphs, Roditty and Zwick, 2002 link and Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components, Lacki, SODA 2011 link
Mon. April 4 S. Pidcock. Linkless and flat embeddings in 3-space and the unknot problem, Kawarabayashi, Kreutzer, Mohar, SoCG 2010. link