Graph-Theoretic Algorithms Spring 2017 Projects

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Exams

Every student is required to do a project, consisting of the following:

• Pick a fairly recent topic in the area of graph-theoretic algorithms (suggestions below)
• Write lecture notes that explain the topic or related topics.
• To do so, read the suggested literature, and find and read further background literature as needed.
• Have a meeting with me where I ask you questions about your lecture notes.

Topics

1. Conflict-free coloring of planar graphs. http://dx.doi.org/10.1137/1.9781611974782.127
   This project has been taken
2. 5-list-coloring planar graphs with some precoloring. http://dx.doi.org/10.1016/j.jctb.2016.06.006
3. Maximum flow in directed planar graphs. http://doi.acm.org/10.1145/1502793.1502798.
   This project has been taken
4. Maximum flow in embedded higher-genus graphs. http://dx.doi.org/10.1137/090766863.
5. Minimum cuts and shortest cycles in directed planar graphs. https://arxiv.org/abs/1703.07964
6. Computing the diameter of planar graphs in subquadratic time. https://arxiv.org/abs/1704.02793
7. Approximating the diameter in planar graphs in linear time. http://doi.acm.org/10.1145/2764910
8. Computing the girth of a planar graph. http://dx.doi.org/10.1137/110832033
   This project has been taken
9. Schnyder woods on higher-genus graphs. http://dx.doi.org/10.1007/s00454-013-9552-7
10. Poly-line drawings of planar graphs that match the lower bound http://dx.doi.org/10.1007/3-540-36379-3_4
11. Simple recognition of Halin-graphs. http://dx.doi.org/10.7155/jgaa.00395
    This project has been taken
12. Maximum clique in multiple interval graphs. http://dx.doi.org/10.1007/s00453-013-9828-6
13. Graph thinness: generalizing interval graphs. https://arxiv.org/abs/1704.00379
14. Induced disjoint paths in circular-arc graphs. http://dx.doi.org/10.1016/j.tcs.2016.06.003
    This project has been taken
15. sim-width for chordal graphs and co-comparability graphs. http://arxiv.org/abs/1606.08087.
16. Hamiltonicity in split graphs. http://dx.doi.org/10.1007/978-3-319-53007-9_28
    This project has been taken
17. Computing boxicity representations of small dimension. http://dx.doi.org/10.1007/s00453-008-9163-5
18. Boxicity and Separation dimension. http://dx.doi.org/10.1007/s00453-015-0050-6
19. Boxicity of embedded graphs. href="http://dx.doi.org/10.1007/s00373-012-1130-x"
20. 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.)
21. Cubicity and bandwidth. http://dx.doi.org/10.1007/s00373-011-1099-x
22. Graph Isomorphism for Unit Square Graphs. http://dx.doi.org/10.4230/LIPIcs.ESA.2016.70
23. Graphs with tree roots. http://dx.doi.org/10.1007/s00453-013-9815-y
24. Graphs with outerplanar roots https://arxiv.org/abs/1703.05102
25. 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.)
26. Treewidth-based dynamic programming in planar graphs. http://dx.doi.org/10.1016/j.dam.2009.10.011
27. Sphere Cut Decompositions and exact algorithms based on them. http://dx.doi.org/10.1007/s00453-009-9296-1
    (This project builds on top of the previous one and could be a group project.)
28. Width-parameters and duality. http://dx.doi.org/10.1016/j.dam.2011.06.028
29. Pathwidth of matroids. http://dx.doi.org/10.1137/1.9781611974331.ch116
30. Cutwidth: Obstructions and FPT-algorithms. http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.15
    This project has been taken
31. Cliquewidth. http://dx.doi.org/10.1007%2Fs002249910009.
32. A width-parameter between treewidth and cliquewidth. http://dx.doi.org/10.1007/s00453-015-0033-7
33. Rankwidth. http://arxiv.org/abs/1601.03800
34. Rankwidth and cliquewidth in trees. http://dx.doi.org/10.1016/j.tcs.2015.04.021
35. Treedepth and how to compute it. http://dx.doi.org/10.1007/978-3-662-43948-7_77.
    This project has been taken
36. Subgraph isomorphism in planar graphs. http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2460.
37. Steiner trees in planar graphs. http://doi.acm.org/10.1145/2601070
    This project has been taken
38. Fast Minor Testing in Planar Graphs. http://dx.doi.org/10.1007/s00453-011-9563-9
39. Recursive Separator Decompositions for Planar Graphs. http://doi.acm.org/10.1145/2488608.2488672
40. Baker-style approaches for "thin" graphs. https://arxiv.org/abs/1704.00125
41. A polynomial-time 5-approximation for treewidth http://dx.doi.org/10.1137/130947374 (due July 14)
42. Bidimensionality of geometric intersection graphs. http://dx.doi.org/10.1007/978-3-319-04298-5_26 (due July 14)

    (The following are some late additions:)

43. A new characterization of chordal graphs. https://arxiv.org/abs/1706.04537
    This project has been taken
44. Efficient subgraph mining on bounded-treewidth graphs. https://doi.org/10.1016/j.tcs.2010.03.030
    This project has been taken
45. Maintaining planar graphs under contraction. https://arxiv.org/abs/1706.10228
46. Shrubdepth, a variation of treedepth and cliquewidth. https://arxiv.org/abs/1707.00359

To claim a project, email me. Be sure to read the paper (superficially) before claiming a project; I usually have not read more than the abstract and cannot guarantee that these papers are indeed suitable for projects.

Lecture notes

• Lecture notes 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.
• Select suitable material from your paper. The papers listed are only an inspiration for where your project might go. For quite a few of them, you might end up following the references from the introduction section instead and review (some) of those results. Your mental goal should be "I want to write an interesting presentation", and not "I must cover all this material".
  More specifically, for topics that are closely related to class-material, you will probably be able to give most details of the algorithm/proof. But for topics that are farther from class-material, your lecture notes should spend much time on motivation, definitions, examples, and how it ties in with cs762 material. You should still state the main idea of the paper, but likely not more than a rough idea of how to prove this.
  Selection appropriate material is part of your project. Both overlength and underlength will be punished.
• The main goal is to create notes that could be used as future cs762 lecture notes. In particular, they 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).
• 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.)
• 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.
• 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.
• 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.

• Submission deadline: Monday, July 10, 23:59pm. Students whose project crucially uses contents of Lecture 17 or 18 may negotiate for a later deadline.
• Late submissions are accepted, but every hour delay leads to one less point (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).
  Put your PDF-files in the "Dropbox" region of assessments on the Learn web page for cs762. (Alternatively, you can email me your PDFs. However, then you cannot revise your submission; the first emailed version will be used.)
• Projects can be done in groups of up to 3 people, but groups of X people should result in lecture notes 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.
• The grade will take the difficulty of the project into account. If your project seems ridiculously easy, think about related things to add (or if you can't think of any, contact me). On the other hand, if your project seems outrageously hard (in particular if you are stuck entirely on some proof), contact me in advance.
• 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.)

1-on-1 Meeting

• I will have read (or at least glanced at) your project report before the meeting, and ask you questions about it.
• 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 bring their copy of the paper (with their annotations) or other study-notes that they created while preparing the project report.
• 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. You are expected to have read more of the paper(s) than what is written in the project report, though for more difficult papers it is acceptable not to have read all of it.

• Wednesday, July 12, 2-2:30 (This slot has been taken)
• Wednesday, July 12, 2:30-3 (This slot has been taken)
• Wednesday, July 12, 3:30-4
• Wednesday, July 12, 4-4:30
• Friday, July 14, 9:30-10
• Friday, July 14, 10-10:30 (This slot has been taken)
• Friday, July 14, 11-11:30 (This slot has been taken)
• Friday, July 14, 11:30-12 (This slot has been taken)
• Friday, July 14, 12:30-1 (This slot has been taken)
• Friday, July 14, 1-1:30 (This slot has been taken)
• Friday, July 14, 2-2:30 (This slot has been taken)
• Friday, July 14, 2:30-3 (This slot has been taken)
• Friday, July 14, 3:30-4 (This slot has been taken)
• Friday, July 14, 4-4:30 (This slot has been taken)

Ideas for getting a better grade on your lecture notes.

• Break the notes down into readable chunks. Group related topics into sections, break them down into subsections if appropriate. Clearly mark what the theorems and what the proofs are.
• 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 reader.
• 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.
• 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.

Webmaster: