[Please remove <h1>]

---

Objectives

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.

References

To be determined.

Schedule

Three hours of lecture per week.

Outline

Planar Graphs (12 hrs)

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.

Trees and Tree-like Graphs (12 hrs)

Techniques for solving NP-complete problems on trees. Generalizations to graphs of bounded pathwidth and treewidth. Implications of the Robertson-Seymour graph minors project.

Perfect Graphs and Intersection Graphs (12 hrs)

Recognition and fast algorithms for problems defined on chordal graphs, comparability graphs, permutation graphs, cographs, interval graphs, circular arc graphs, and claw-free graphs.