Graph-Theoretic Algorithms Spring 2024 Projects

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Final

Every student is required to do a project, which can be summarized as "be the teacher for one lecture". This means the following:

• Pick a fairly recent topic in the area of graph-theoretic algorithms. Some pointers are below, but selecting the actual material and finding and reading related literature is part of the project.
  
• Write lecture notes that explain the topic in detail, with lots of pictures.
• Record a video where you help the viewer understand the lecture notes more easily, typically by going over them and highlighting important parts.
  Two projects are different (let's call them presentation-projects): Here you do not have to record a video, but you must teach half a class, and the topic is more-or-less fixed by me.
• Have an 1-on-1 meeting with me where I ask you questions about your topic.

Topics

Topics that have been chosen

• No projects have been chosen yet.

The two presentation-projects

• Twinwidth. A fairly recent sequence of paper on a new width parameters that combines many existing results but is still strong enough to have algorithmic implications. See the DBLP page of E.Bonnet for many possible references.
  You should define what this is, prove that it is constant for some of our graph classes (e.g. outerplanar graphs or maybe even for planar graphs), why it is useful algorithmically (see e.g. https://arxiv.org/abs/2207.07708), and add other results as you see fit to make for an interesting presentation.
• Planar Graph Product Structure Theorem (see e.g. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v29i2p51 for an improved variant).
  You should explain what the statement is, and give at least a sketch of the proof (ideally the one with row treewidth 6). Then cover some of the implications, and add generalizations to other graph classes as you see fit to make for an interesting presentation.

If you want to do one of these two projects, email me about it in May. In case of multiple candidates, I will decide in early June among them (mostly based on how well I feel that they can explain things to me in assignment meetings or office hours). The actual presentation will be on June 28 at class-time and should be approximately 35 minutes long to allow for switchover time and questions.

Some possible starter-papers

The papers are (very roughly) sorted by where the corresponding topics were covered in class.

1. Connected max cut in graphs without K5-e as minor (2019). https://arxiv.org/abs/1903.12641
2. Randomized algorithms for cut-uncut on planar graphs (2023). https://arxiv.org/abs/2305.01314
3. Simpler Shortest Path in Planar Digraphs (2023) https://arxiv.org/abs/2111.07360
4. Minimum cuts and shortest cycles in directed planar graphs (2017). https://arxiv.org/abs/1703.07964
5. Multicommodity flows in planar graphs (2020). https://arxiv.org/abs/2007.01280
6. Computing the diameter of planar graphs in subquadratic time (2020). https://arxiv.org/abs/1704.02793
7. Approximating the diameter in planar graphs in near-linear time (2016). http://doi.acm.org/10.1145/2764910, see also https://link.springer.com/article/10.1007/s00453-019-00570-z
8. Oriented diameter of planar triangulations (2022). https://arxiv.org/abs/2203.04253
9. Decremental 3-connected components of for planar graphs (2018). https://arxiv.org/abs/1806.10772
10. Convex Grid Drawings with good resolution (2022). https://arxiv.org/abs/2203.04253
11. Computing Circle Packing Representations of Planar Graphs (2020). https://epubs.siam.org/doi/10.1137/1.9781611975994.174
12. Parallel Planar Subgraph Isomoprhism (2020). https://arxiv.org/abs/2007.01199
13. Massively Parallel Computation on Embedded Planar Graphs (2022) https://arxiv.org/abs/2204.09035
14. List-color extendability on outerplanar graphs (2020). https://arxiv.org/abs/1912.07679.
15. Every Property of Outerplanar Graphs is Testable (2016). https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.21
16. Shortest Beer Path Queries in Outerplanar Graphs (2021). https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.62
17. The Canadian Traveller Problem on outerplanar graphs (2024). https://arxiv.org/abs/2403.01872
18. Succinct Data Structures for some subclasses of planar graphs (2021). https://arxiv.org/abs/2108.10776
19. Partitioning cactus graphs (2022). https://arxiv.org/abs/2001.00204.

20. Maximum cut in (unit) interval graphs (2020). https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.57 but see also https://arxiv.org/abs/2012.09804 and https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.7
21. Assistance and Interdiction Problems on Interval Graphs (2021). https://arxiv.org/abs/2107.14550
22. LexDFS (not lexBFS!) in chordal graphs (2020). https://arxiv.org/abs/2005.03523
23. Computing a clique tree in chordals graphs with MLS (2016). https://arxiv.org/abs/1610.09623
24. Testing isomorphism of chordal graphs of bounded leafage (2021). https://arxiv.org/abs/2107.10689, see also https://arxiv.org/abs/2111.10910.
25. Approximating independent set in rectangle intersection graphs (2021). https://arxiv.org/abs/2106.00623, but see also https://arxiv.org/abs/2101.00326.
26. Graph thinness: generalizing interval graphs (2018). https://arxiv.org/abs/1704.00379
27. Maximum clique in disk graphs (2021). https://arxiv.org/abs/2007.03492, see also https://arxiv.org/abs/2303.07645
28. Minimum (s,t)-cuts in disk graphs (2022). https://arxiv.org/abs/2005.00858
29. Graph Isomorphism for Unit Square Graphs (2016). http://dx.doi.org/10.4230/LIPIcs.ESA.2016.70
30. Matching in co-comparability graphs (2018). https://arxiv.org/abs/1703.05598
31. Recognizing Proper Tree Graphs (2020). https://arxiv.org/abs/2011.11670
32. Well-partitioned chordal graphs, a generalization of split graphs (2020). https://arxiv.org/abs/2002.10859
33. Intersection model for strong chordal graphs (2021) https://arxiv.org/abs/1911.11494
34. Domination in Petri Nets (2020). https://arxiv.org/pdf/2001.04374.pdf
35. MaxCut in proper interval graphs (2020). https://arxiv.org/abs/2006.03856.
36. MaxCut in permutation graphs (2022). https://arxiv.org/abs/2202.13955
37. Thinness, a generalization of interval graphs (2021). https://arxiv.org/abs/2006.16887
38. Improving algorithms for recognizing perfect graphs (2022). https://arxiv.org/abs/2207.07613.

39. Knot diagrams of treewidth 2 (2019). https://arxiv.org/abs/1904.03117
40. Treewidth of Hanoi graphs (2020). https://arxiv.org/abs/2005.00179
41. Graphs with outerplanar roots or pathwidth-2 roots (2018). https://arxiv.org/abs/1703.05102
42. Automata networks and boundeed treewidth (2021). https://arxiv.org/abs/2005.11758.
43. Pathwidth of matroids (2016). http://dx.doi.org/10.1137/1.9781611974331.ch116
44. Treewidth of triangulated 3-manifolds (2021). https://arxiv.org/abs/1712.00434
45. Treewidth is hard on cubic graphs (2023). https://arxiv.org/abs/2206.00752.
46. Faster approximation for treewidth (2023). https://arxiv.org/abs/2104.07463
47. Dynamic maintenance of treewidth (2023). https://arxiv.org/abs/2304.01744
48. Gerrymandering over paths and trees (2021). https://arxiv.org/abs/2102.08905
49. Rectilinear Planarity Testing in SP-graphs (2020). https://arxiv.org/abs/2008.03784v3
50. Maximum common subgraphs in SP-graphs (2017). https://arxiv.org/abs/2111.07628
51. Treewidth and stable marriage (2017). https://arxiv.org/abs/1707.05404
52. Treewidth and Linear Programming (2023). https://arxiv.org/abs/2011.05365
53. Sinkhorn's algorithm and treewidth (2023). https://arxiv.org/abs/2301.06741
54. Disjoint paths and treewidth (2015). https://arxiv.org/abs/1512.01829
55. Recognizing map graphs of bounded treewidth (2022). https://arxiv.org/abs/2206.14898
56. Embedding Phylogenetic trees in networks of low treewidth (2022). https://arxiv.org/abs/2207.00574
57. Frechet distance in graphs of bounded treewidth (2020). https://arxiv.org/abs/2001.10502.
58. Faster DP for domination problems on treewidth (2020). https://arxiv.org/abs/2006.01588.
59. Crossing number parameterized by vertex cover (2019). https://arxiv.org/abs/1906.06048
60. Markov Chain analysis and treewidth (2020). https://arxiv.org/abs/2004.08828
61. Using DBMS and treewidth for counting (2021). https://arxiv.org/abs/2001.04191
62. Faster DP on graph decompositions (2018). https://arxiv.org/abs/1806.01667
63. Independent set and bipartite pathwidth (2020). https://arxiv.org/abs/1812.03195
64. Connected pathwidth (2022). https://arxiv.org/abs/2004.11937
65. Directed branchwidth (2023). https://arxiv.org/abs/2009.08903
66. Treedepth and how to compute it (2019). https://arxiv.org/abs/2004.08959.
67. Tree-cut width and applications (2022). https://arxiv.org/abs/2206.00752.
68. Cops, Robber and medianwidth parameters (2016). https://arxiv.org/abs/1603.06871

69. Steiner cuts in planar graphs (2019). https://arxiv.org/abs/1912.11103
70. Simple algorithm for a cycle separator (2018). https://arxiv.org/abs/1709.08122
71. Baker-style approaches for "thin" graphs (2017). https://arxiv.org/abs/1704.00125
72. Bidimensionality of geometric intersection graphs (2014). http://dx.doi.org/10.1007/978-3-319-04298-5_26

Lecture notes

• Lecture notes should cover material that would fit into an 80-minute class, or as much as in one of the shorter chapters of the lecture notes (the chapters on cutwidth and separators are good examples). So aim for 6-8 pages (using those margins and fonts); more are ok if you have lots of pictures.
• Lecture notes should be easier to read than the original. You should provide lots of pictures and examples. For algorithms, it is strongly recommended to create a running example (ideally one that illustrates the various cases or difficulties that could arise). For complicated multi-case proofs, pick the most relevant situation(s) and explain this in great detail, then skip the other cases. For algorithms for constant treewidth, perhaps explain it only for treewidth 2 or 3.
• You must not copy from your references verbatim; rephrase everything in your own words. You are more than welcome to improve on your references if you see a simplification. Indicate (e.g. with a footnote) if there is a major part that you have developed yourself.
• You should tie your topic with the material that has been covered in class. E.g., if you are studying another graph class, say how it relates to graph classes that we have seen. If you study some width parameter, say whether it is larger/smaller/incomparable to the width parameters that we have seen.
  You should also use the same notations than what was used in class. (If you really want to use the notations from the paper instead, then at least point out in the notes what the corresponding notation from class was.)
• Break the topic down into easily understandable chunks. Group related topics into sections, break them down into subsections if appropriate. Clearly mark what the theorems and what the proofs are.
• Every step of what you write should be understandable to someone who has taken cs762. You need not (in fact, should not) define terms that we saw in class, except for perhaps a 1-sentence "Recall that...". On the other hand, obscure explanations (and in particular, an "it is obvious" when it isn't obvious) will reduce the grade.
• Motivate what you're doing. Giving the history of a topic (who did what when, in parallel with who?) is often entertaining, so if there is a colorful history, give it. If there are nice applications of your graph class/result, mention it. Relate your topic to what we've seen in class. Anything to excite the audience.
• Explain what you're doing. The good old suggestion "Say what you're going to do. Then do it. Then say what you just have done." applies. Every section (and most subsections) should start with a brief outline of what they contain. Most proofs benefit from first giving the overall idea of the proof, and then giving the nitty-gritty details.
• Pictures are really helpful. While you should avoid giving a definition only in a picture, it helps a lot to give the definition in the text and illustrate it in a picture. Similar holds for proof ideas. Pictures do not count towards the (loosely defined) page-limit, so do not skimp on pictures. Recall, they may be handdrawn and scanned/photographed.
• If you really can't figure out a step in your reference within a reasonable amount of time, then indicate in the lecture notes where the difficulty was. This will not be punished if the difficulty was beyond what can be expected.
• Be sure to include references to all sources you have used, and indicate which one(s) were your main references. Use full references (author, title, journal/conference-name, pages, year) and preferably include a DOI-link.
• Definitely use a spell checker, for example (under linux) "ispell filename.tex". Grammar errors are excusable (especially for non-native-speakers), as long as the meaning is clear. Spelling errors are not.

Videos:

• My recommendation would be to make the video an `annotation of the notes'. This means that you have your lecture notes in front of you, and you `walk through' them for the purpose of the reader, highlighting the important parts and perhaps adding further small examples. (In 2020 I taught cs762 via such videos; I can make selected videos of that available if you would like to see some examples.)
  There are other options if you'd rather not do an annotation of the nodes, e.g. you could create slides (more like a research presentation) or set up a camera that films you while you teach in a classroom (more like a real-life lecture). The choice is yours.
• Do not simply read out your notes. Instead, highlight the parts that are really important, and perhaps draw further examples. (On the other hand, straightforward-to-read parts of the notes, such as history or motivation, can probably be skipped.)
• Giving the nitty-gritty details of a proof in a time-restricted presentation is rarely helpful. Focus on the big picture, give the ideas of the proof (and perhaps do one illustrative case), but do not cover all details. The goal of the video should most be `engage the viewers so that they actually want to read the notes', not to give a complete proof.
• The presentation must be pre-recorded. Breaking it into multiple small pieces of (e.g. for easier downloading and viewing) is fine.
• The total viewing time should not exceed 30 minutes. This is not a rigid limit, but if you exceed it then the extra time had better been extremely helpful for understanding.
• It's the content that counts, not the quality of recording. While you should try to find a decent microphone (and camera if you don't use a screencast), I will not deduct for quality of video as long as it is understandable. Do not waste time on making fancy intros/transitions.

Evaluation

Material selection is also a criterion. How well did you relate your topic to cs762 material? Did you give a well-rounded picture of what is known in this area, before going into the details for some of the results? Did you choose material at approximately the right level for cs762 students? Making your project super-easy to understand by covering only trivialities will lead to deduction. Excessive overlength may also lead to deduction.

Quality of presentation is also quite important, especially for the lecture notes. Videos and 1-on-1-meetings will be evaluated on content only, and not on the quality of the technology used to deliver it (as long as it is usable).

Technicalities:

• Late submissions are accepted, but every day of delay leads to 10 fewer points (out of 100) on the grade.
• Lecture notes should be LaTeX. Talk to me if this poses a significant problem. Pictures may be scans or photos of handdrawings. Pictures must not rely on color (I will likely read a black-and-white printout.)
• Submit a PDF-file with your notes, as well as PDF-files of your main references (typically 1-2 papers).
• Videos should be a .mp4 or .webm file, though I am willing to accept other formats if you check beforehand with me that my computer can process it.
• Submit your files in the "Dropbox" region of assessments on the Learn web page for cs762. If you have trouble uploading your video, try uploading a link to a webpage that has the video instead. If all else fails, email me a link to where the video can be found. (Do not email me the video directly; my email inbox will crash.)
• Projects can be done in groups of up to 3 people, but groups of X people should result in lecture notes/videos that cover X times as much material.
• You are allowed to collaborate on this project, even with fellow students that aren't project partners. I recommend exchanging lecture notes with each other and critiquing, but will not coordinate this. Acknowledge any help that you have received in the lecture notes.
• I reserve the right to use part of your lecture notes in future versions of the cs762 lecture notes (with an acknowledgments to you in the intro).