To give the student further exposure to the design, analysis, and application of algorithms for problems defined on graphs.
Students are expected to have basic knowledge of algorithm design and analysis.
To be determined.
Three hours of lecture per week.
Linear-time planarity testing and embedding algorithms. Decomposing planar graphs. Series-parallel, outerplanar, k-outerplanar graphs; recognition and fast algorithms for problems defined on these classes.
Techniques for solving NP-complete problems on trees. Generalizations to graphs of bounded pathwidth and treewidth. Implications of the Robertson-Seymour graph minors project.
Recognition and fast algorithms for problems defined on chordal graphs, comparability graphs, permutation graphs, cographs, interval graphs, circular arc graphs, and claw-free graphs.