Graph-Theoretic Algorithms
Spring 2020

UW Logo


Outline, detailed information, lecture summaries.
LEARN page: (accessible only to registered students)
Announcements, lecture-by-lecture material, forum.
Therese Biedl

Room DC2341, x34721 (not while UW is closed)
Office hours (online within LEARN): WF 3-3:30pm or by appointment.
Online-availability: I read email at least once per workday, and usually more often, but not continually. So even urgent questions may need a few hours to get answered. I read very little email on weekends.
Lecture Notes: Full lecture notes are available on LEARN.
Individual sets of pages, compatible with each lecture, will be posted.
Videos: Short videos will be posted on LEARN.
These re-inforce the lecture notes, but are likely not sufficient to learn the material by themselves. Most learning should come from reading the lecture notes pages.
Forum: LEARN has a forum for exchanges between students. In past offerings this wasn't used, but we may use it if students find it useful. (Urgent questions should be sent to me by email.)
Other fesources: Two online resources are recommended:
  • More graph classes than you ever knew existed, with relationships between them and complexities of various problems.

  • wikipedia. Normally one should be careful in using wikipedia as a research resource, since it is not curated. However, most web pages on relevant topics (e.g. treewidth and pathwidth) were written by David Eppstein and seem to be monitored by him. David is a prominent researcher in the field; if you see his name frequently in the revision history then the page is probably trustworthy.
Also numerous other good textbooks:
  • Graph Classes: A Survey (A. Brandstädt, V.B. Le, J.P. Spinrad), SIAM Monographs on Discrete Mathematics and Applications, SIAM, 1999.
    Excellent overview of graph classes with lots of references, but no proofs.
    Available from the WLU library, call number QA166 .B73.

  • Planar graphs: theory and algorithms (T. Nishizeki, N. Chiba), North-Holland publisher, 1988.
    Decent reference for planar graphs, but a bit old.
    Available from the UW library, call number QA1.N855 no. 140.

  • Planar graph drawing (T. Nishizeki, Md. S. Rahman), Lecture Notes Series on Computing, Volume 12, World Scientific, 2004.
    Newer book with focus on drawing graphs, but also some background on planar graphs in general. Sadly not available from the UW libraries unless you happen to be a Guelph user.

  • Algorithmic Graph Theory and Perfect Graphs (M.C. Golumbic), Academic Press, New York, 1980. 2nd edition 2004.
    Great reference for interval graphs and friends, but a bit out of date. (The 2nd edition is essentially the same as the 1st, except for an epilogue chapter.)
    Available from the UW library, call number (1st ed.) QA166.G64 1980 and (2nd ed.) QA166.G64 2004.

  • H. Bodlaender and A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal 51 (3), 255-269, 2008.
    One of the (many) review articles that Bodlaender wrote about treewidth and its algorithmic applications. Some of the older articles (search for MFCS 1998, TCS 1998 or SOFSEM 2005) go more in-depth into some of these topics, but of course are more outdated.

  • Graph Theory (R. Diestel), Springer Verlag, 1997 (and multiple later edition).
    Good for minor theory; also discusses planar graphs and partial k-trees.
    Available from the UW library, call number QA166.D51413 2000.
    The book website has a free preview version available electronically.

Last modified: 04/30/2020