Graph-Theoretic Algorithms Spring 2020 Projects

Resources

Outline

Summaries

Project

Exams

Delivery

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 topic visually, typically by going over the pictures and the examples.
• Have an online meeting with me where I ask you questions about your topic.

Topics

Topics that have been chosen

• Highway dimension, treewidth and shortest paths. https://arxiv.org/abs/1502.04588.
• Parametrized complexity of virtual network embeddings. https://dl.acm.org/doi/10.1145/3314212.3314214.
• Independent set in max-point tolerance graphs and other intersection graphs. https://www.sciencedirect.com/science/article/abs/pii/S0166218X15004266.
• A Game-Theoretic Approach to Courcelle's theorem. https://arxiv.org/abs/1104.3905
• Planar graphs have bounded queue-number. https://ieeexplore.ieee.org/document/8948698.
• Disjoint paths in split graphs. https://link.springer.com/content/pdf/10.1007/s00224-014-9580-6.pdf.

Some possible starter-papers

1. Disjoint paths in planar graphs in linear time. https://arxiv.org/abs/1907.05940
2. Conflict-free coloring of planar graphs. http://dx.doi.org/10.1137/1.9781611974782.127
3. 5-list-coloring planar graphs with some precoloring. http://dx.doi.org/10.1016/j.jctb.2016.06.006
4. List-color extendability on outerplanar graphs. https://arxiv.org/abs/1912.07679. (These two projects could well be a group project.)
5. Maximum flow in embedded higher-genus graphs. http://dx.doi.org/10.1137/090766863.
6. Minimum cuts and shortest cycles in directed planar graphs. https://arxiv.org/abs/1703.07964
7. Computing the diameter of planar graphs in subquadratic time. https://arxiv.org/abs/1704.02793
8. Approximating the diameter in planar graphs in linear time. http://doi.acm.org/10.1145/2764910
9. Computing the girth of a planar graph. http://dx.doi.org/10.1137/110832033
10. Schnyder woods on higher-genus graphs. http://dx.doi.org/10.1007/s00454-013-9552-7
11. Homothetic triangle representations of planar graphs. https://arxiv.org/abs/1908.11749
12. Decremental 3-connected components of for planar graphs. https://arxiv.org/abs/1806.10772
13. Token sliding on cactus graphs. https://arxiv.org/abs/1705.00429
14. Partitioning cactus graphs. https://arxiv.org/abs/2001.00204. (These two projects could well be a group project.)

15. Matching in co-comparability graphs. https://arxiv.org/abs/1703.05598
16. Computing a clique tree in chordals graphs with MLS. https://arxiv.org/abs/1610.09623
17. LexDFS (not lexBFS!) in chordal graphs. https://arxiv.org/abs/2005.03523
18. Maximum clique in multiple interval graphs. http://dx.doi.org/10.1007/s00453-013-9828-6
19. Graph thinness: generalizing interval graphs. https://arxiv.org/abs/1704.00379
20. Induced disjoint paths in circular-arc graphs. http://dx.doi.org/10.1016/j.tcs.2016.06.003
21. sim-width for chordal graphs and co-comparability graphs. http://arxiv.org/abs/1606.08087.
22. Hamiltonicity in split graphs. http://dx.doi.org/10.1007/978-3-319-53007-9_28
23. Well-partitioned chordal graphs, a generalization of split graphs. https://arxiv.org/abs/2002.10859
24. Coloring intersection graphs of L-shapes. https://arxiv.org/abs/2002.10755
25. Minimum (s,t)-cuts in disk graphs. https://arxiv.org/abs/2005.00858.
26. Boxicity and Separation dimension. http://dx.doi.org/10.1007/s00453-015-0050-6
27. Boxicity of embedded graphs. http://dx.doi.org/10.1007/s00373-012-1130-x
28. Box representations of embedded graphs. http://dx.doi.org/10.1007/s00454-016-9837-8
    (This project builds on top of the previous one and could be a group project.)
29. Cubicity and bandwidth. http://dx.doi.org/10.1007/s00373-011-1099-x
30. Graph Isomorphism for Unit Square Graphs. http://dx.doi.org/10.4230/LIPIcs.ESA.2016.70
31. Independent set on P6-free graphs. https://arxiv.org/abs/1707.05491
32. Isomorphism of circular-arc graphs. https://arxiv.org/abs/1903.11062
33. Intersection model for strong chordal graphs https://arxiv.org/abs/1911.11494
34. Domination in Petri Nets. https://arxiv.org/pdf/2001.04374.pdf
35. MaxCut in proper interval graphs. https://arxiv.org/abs/2006.03856.
36. Thinness, a generalization of interval graphs. https://arxiv.org/abs/2006.16887

37. Knot diagrams of treewidth 2. https://arxiv.org/abs/1904.03117
38. Graphs with tree roots. http://dx.doi.org/10.1007/s00453-013-9815-y
39. Graphs with outerplanar roots https://arxiv.org/abs/1703.05102
40. Graphs with roots of pathwidth 2 https://arxiv.org/abs/1703.05102
    (These two projects use the same paper and should likely be a group project.)
41. Treewidth and stable marriage https://arxiv.org/abs/1707.05404
42. Maximum common subgraphs in SP-graphs https://arxiv.org/abs/1512.01829
43. Frechet distance in graphs of bounded treewidth. https://arxiv.org/abs/2001.10502.
44. Faster DP for domination problems on treewidth. https://arxiv.org/abs/2006.01588.
45. Automata networks and boundeed treewidth. https://arxiv.org/abs/2005.11758.
46. Pathwidth of matroids. http://dx.doi.org/10.1137/1.9781611974331.ch116
47. Connected pathwidth. https://arxiv.org/abs/1802.05501
48. Crossing number parameterized by vertex cover. https://arxiv.org/abs/1906.06048
49. Independent set and bipartite pathwidth. https://arxiv.org/abs/1812.03195
50. Geodetic sets and hardness even in restricted graph classes https://arxiv.org/abs/2006.16511
51. Treedepth and how to compute it. http://dx.doi.org/10.1007/978-3-662-43948-7_77.
52. MILP and small treedepth. https://arxiv.org/abs/1912.03501 (These two projects could well be a group project.)
53. Using DBMS and treewidth for counting. https://arxiv.org/abs/2001.04191
54. Width-parameters and duality. http://dx.doi.org/10.1016/j.dam.2011.06.028
55. Faster DP on graph decompositions. https://arxiv.org/abs/1806.01667
56. Treewidth of triangulated 3-manifolds. https://arxiv.org/abs/1712.00434
57. Cutwidth: Obstructions and FPT-algorithms. http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.15
58. Cops, Robber and medianwidth parameters. https://arxiv.org/abs/1603.06871
59. Shrubdepth, a variation of treedepth and cliquewidth. https://arxiv.org/abs/1707.00359
60. A width-parameter between treewidth and cliquewidth. http://dx.doi.org/10.1007/s00453-015-0033-7
61. Tree- and path-chromatic numbers. https://arxiv.org/abs/2002.05363
62. Rankwidth. http://arxiv.org/abs/1601.03800
63. Rankwidth and cliquewidth in trees. http://dx.doi.org/10.1016/j.tcs.2015.04.021

64. Steiner trees in planar graphs. http://doi.acm.org/10.1145/2601070
65. Steiner cuts in planar graphs. https://arxiv.org/abs/1912.11103
66. Fast Minor Testing in Planar Graphs. http://dx.doi.org/10.1007/s00453-011-9563-9
67. Recursive Separator Decompositions for Planar Graphs. http://doi.acm.org/10.1145/2488608.2488672
68. Simple algorithm for a cycle separator. https://arxiv.org/abs/1709.08122
69. Baker-style approaches for "thin" graphs. https://arxiv.org/abs/1704.00125
70. A polynomial-time 5-approximation for treewidth http://dx.doi.org/10.1137/130947374
71. Product structure of planar graphs. 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:

• It is recommended (but not required) that you imitate what I did for the class material: "Walk through" your lecture notes, highlighting the important parts and perhaps adding further examples. But other methods (narrate a slide show or or film yourself in front of a board) are acceptable.
• 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.)
• The presentation must be pre-recorded. Breaking it into multiple small pieces of about 5 minutes is recommended (for easier downloading and viewing).
• 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 use one), I will not deduct for quality of video as long as it is understandable. Do not waste time on making fancy intros/transitions.

1-on-1 meeting:

• I will have read your lecture notes and watched your video. I may or may not have read parts of the relevant paper(s). If everything was perfectly clear to me, then the meeting will probably be quite short. But usually I'll have a few question or will ask for further explanation.
• You need not bring or prepare anything for the meeting. In particular, this is not a presentation; do not prepare slides. Some students find it helpful for answering questions to have their copy of the paper (with their annotations) or other study-notes that they created while preparing the project report. You should also have your video handy, in case I ask questions about a particular minute.
• The 1-on-1 meeting will be evaluated primarily based on your ability to answer questions about your topic. Be ready to justify any claim in your lecture notes in detail, or clarify things by giving a different example. I may also ask about why you didn't include some parts of the paper(s).
• These 1-on-1 meetings may well be combined with the final, especially if I do not have a lot of questions.

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

Webmaster: