Graph-Theoretic Algorithms Spring 2024 Schedule

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Final

This is a tentative schedule; references should be approximately correct for lectures that have passed, but are still very much in flux for future lectures.The reference means the lecture notes.

For lack of time (and because we really should reach the separator theorem), a number of interesting topics will to be skipped, but we may have time to cover some of them in late June. If there are topics that you would especially liked to see covered, then let the instructor know by June 15. Possible topics that could be covered (in order where they fit in class) are:

• Maximum cut in planar graphs (Chapter 4)
• Matching in bridgeless planar graphs (not in course notes)
• Planarity testing (Chapter 6)
• Straight-line drawings with small grid-size (not in course notes)
• 4-connected triangulations and Hamiltonian cycles therein (Chapter 7.4)
• 3-connected planar graphs and Tutte paths in linear time (not in course notes)
• Various `how to reduce run-time to O(n)', e.g. making triangulated, computing canonical order
• Branchwidth, carvingwidth, antipodalities, and how to compute them (not in course notes)
• Pathwidth, cutwidth and complexity of computing widths (Chapter 14.2-14.3)
• Treewidth, grids and algorithmic implications (Chapter 18)
• A glimpse at the graph minor theorem (Chapter 19)