Registration Deadline: September 20, 2026

Instructors: Professor Prosenjit Bose & Dr. Bobby Miraftab, Carleton University

Course Dates: 
Mid-Semester Break: 
Lecture Time: 
Office Hours: 

Registration Fee:

• Students from our Principal Sponsoring & Affiliate Universities: Free
• Other Students: CAD$500

Capacity Limit: 

Format: 

Course Description

This course provides a graduate-level exploration of graph algorithms and structural graph theory. The emphasis is on algorithm design, mathematical analysis, and theoretical foundations of problems on graphs. Topics include graph traversal, spanning trees, network flows, matchings, graph coloring, planar graphs, as well as advanced topics such as geometric graphs, spectral graph theory, random graphs, and tree-decompositions.

The course blends proofs of correctness and complexity with structural insights drawn from modern graph theory. Prerequisites include discrete mathematics and a basic background in graduate-level algorithms. No advanced programming experience is required; basic familiarity with Python and the networkx library is sufficient.

Learning Objectives

Upon completion of the course, students will be able to:

• Formally analyze classical and modern graph algorithms.
• Prove correctness and derive complexity bounds for graph algorithms.
• Apply structural graph theory techniques to algorithmic problems.
• Understand and use geometric and spectral methods on graphs.
• Read, present, and critically assess research papers in graph algorithms.

Textbooks and Recommended Reading

• Introduction to Algorithms (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein). Core algorithmic background.
• Algorithm Design (J. Kleinberg & E. Tardos). Greedy methods, flows, matchings, and general design paradigms. The book website provides a free electronic preview.
• Graph Theory (R. Diestel), Springer, sixth edition. Strong reference for minors; also discusses planar graphs and partial k-trees. The book website provides a free electronic preview.
• Graph Classes: A Survey (A. Brandst ̈adt, V. B. Le, J. P. Spinrad), SIAM Monographs on Discrete Mathematics and Applications, SIAM, 1999. Excellent overview of graph classes with many references (mostly survey-style, few proofs).
• Algorithmic Graph Theory and Perfect Graphs (M. C. Golumbic), Academic Press, New York, 1980; 2nd ed. 2004. Great reference for interval graphs and related perfect graph classes (the 2nd ed. is largely the 1st, with an added epilogue).
• Combinatorial Optimization on Graphs of Bounded Treewidth, H. L. Bodlaender and A. M. C. A. Koster, Survey of treewidth and algorithmic applications; earlier surveys (e.g. MFCS 1998, TCS 1998, SOFSEM 2005) go deeper but are older. Avaliable here.
• Selected research papers and surveys for advanced topics (assigned throughout the course).

Weekly Topics and Schedule

• Module I: Algorithmic and Graph-Theoretic Foundations
• Week 1: Graph Definitions and Representations - Basic graph and algorithmic terminology; adjacency lists and matrices; connectivity; motivating examples from networks.
• Week 2: Graph Traversal Algorithms - Breadth-first search and depth-first search; connected components; articulation points and bridges; topological sorting and strongly connected components, chordal graphs.
• Module II: Core Topics in Algorithmic Graph Theory
• Week 3: Spanning Trees and Minimum Spanning Trees - Trees and forests; Kruskal’s and Prim’s algorithms; correctness proofs and cut properties.
• Week 4: Network Flows and Minimum Cuts - Ford-Fulkerson method; augmenting paths; max-flow min-cut theorem; Dinic’s and Push-Relabel algorithms; bipartite matching and Hall’s theorem.
• Week 5: Advanced Matching Algorithms - Hopcroft-Karp algorithm for bipartite matching; high-level overview of Edmonds’ Blossom algorithm; assignment and weighted matching problems.
• Week 6: Graph Coloring and Planar Graphs - Vertex coloring and chromatic number; greedy algorithms and limitations; NP-hardness of coloring; planar graphs, Euler’s formula, Kuratowski’s theorem, planar embeddings and planar duality.
• Module III: Advanced Topics in Algorithmic Graph Theory
• Week 7: Geometric Graphs - Geometric graph models; unit disk graphs and intersection graphs; connectivity properties; geometric separators and algorithmic implications.
• Week 8: Spectral Graph Theory - Adjacency and Laplacian matrices; eigenvalues and structural properties; algebraic connectivity and spectral clustering.
• Week 9: Random Graphs - Classical random graph models; thresholds for connectivity and other properties; probabilistic methods in graph theory.
• Week 10: Tree-Decompositions and Treewidth - Tree-decompositions, bags, adhesion sets; width and treewidth; canonical examples (trees, cycles, cliques, grids); treewidth as a measure of tree-likeness.
• Week 11: Structure of Tree-Decompositions - Equivalent characterizations of bounded treewidth; separators and balanced separators; optimal and minimal-width decompositions; nice tree-decompositions (overview).\
• Week 12: Algorithms on Bounded Treewidth Graphs - Dynamic programming on tree-decompositions; applications to Vertex Cover, Independent Set, Dominating Set, and $k$-Coloring; algorithmic meta-theorems (Courcelle’s theorem, stated without proof).

Assignments and Projects

• Weekly Assignments: Students will submit a written assignment every week. Each assignment will consist of 4–5 problems related to that week’s material. Problems emphasize proofs, structural reasoning, and algorithmic analysis. Clear justification and rigorous explanations are required.
• Paper Presentations: In place of a midterm exam, students will select a paper from a list of research articles in graph algorithms. Presentations will be scheduled toward the end of the semester. Each student (or small group, for longer papers) will present:
• the central problem addressed,
• the main results and techniques,
• connections to course material,
• and a critical assessment of the contributions.

Evaluation

• Weekly Problem Sets: 50%
• Paper Presentation: 25%
• Final Exam: 25%

Project Paper Options

Some possible papers are listed below. 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, see the references in the course notes.

• Every planar graph is the intersection graph of segments in the plane, Chalopin, Gonçalves, STOC 2009.
• On grid intersection graphs, Hartman, Newman, Ziv, Discrete Math. 1991. (bipartite planar graphs as intersection of line segments)
• Triangle contact representations and duality, Gonçalves, Lévêque, Pinlou, Graph Drawing 2010.
• Triangle-free planar graphs as segment intersection graphs, de Castro, Cobos, Dana, JGAA 2002.
• Computing the Independence Number of Intersection Graphs, Fox and Pach, SODA 2011.
• Unit Rectangle Visibility Graphs, Dean, Ellis-Monaghan, Hamilton, Pangborn, Combinatorics 2008.
• Graph searching, and a minimax theorem for tree-width, Seymour and Thomas, JCTB 1993.
• Schnyder Greedy Routing Algorithm, He, Zhang, TAMC 2010.
• Schnyder embeddings for non-triangulated graphs, in Geometric Graphs and Arrangements, Felsner, 2004.
• Map graphs, Chen, Grigni, Papadimitriou, JACM 2002.
• New Linear-Time Algorithms for Edge-Coloring Planar Graphs, Cole and Kowalik, Algorithmica 2008.
• Contact representations of planar graphs with cubes, Felsner, Francis.
• Treewidth and pathwidth of permutation graphs, Bodleander, Kloks, Kratsch, SIAM J. Disc. Math., 1995.
• On Coloring Unit Disc Graphs, Graf, Stumpf, Weisenfels, Algorithmica 1998.
• Graph Product Structure Theorem.
• A bound on the chromatic number of the square of a planar graph, 2005.

Course Summary

This course has several objectives. We will begin by studying core concepts in graph theory, providing a broad introduction to the area and the main techniques used. We will then explore the algorithmic side of graph-theoretic problems, with an emphasis on how structural results in graph theory guide the design of efficient algorithms for fundamental and practical optimization problems.