# CS 762 Graph-Theoretic Algorithms

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