Algorithms for Planar Graphs (Summer 2017)
|
The exam will be in PZ 1006 please sign into the list |
A planar graph is a graph that can be drawn in the plane such that two edges only cross in a common end vertex. In this lecture we will discuss how to exploit properties of planar graphs in order to solve problems more efficiently than on general graphs. |
General Information
| Lecture (S. Cornelsen) | Mon 13:30-15:00 (M 630) |
| Tutorial (J. Müller) | Wed 15:15-16:45 - fortnightly (Y 311) |
| Exams | 1st date: 24th of July 2017 in PZ 1006, please sign into the list during the lecture or the tutorial 2nd date: to be announced |
Assignments
The assignments are made available on this webpage as a PDF-file (in English) every Monday after the lecture.The editing time for each homework is almost one week.
- It is due on the next Monday at 13:15.
- The assignments have to be delivered in written form either in English or German.
- You have to submit them electronically to pg_u_S17@inf.uni-konstanz.de (one PDF only!!).
- Please follow the naming schema uXX_name1_name2.pdf, where XX indicates the number of the assignment.
The requirements for the admittance to the final exam are 50 percent of the total score of the assignments and regular attendance at the tutorials. In writing up your assignments, be as clear, precise, and concise as possible. Understandability will be an important factor in the scoring of the assignments. Regular attendance is considered especially for borderline cases.
You are permitted and encouraged to work in groups of two.
| No. | Posted | Due Date | Tutorial | Download |
|---|---|---|---|---|
| 1 | 24.04.2017 | 08.05.2017 | 10.05.2017 | |
| 2 | 08.05.2017 | 15.05.2017 | 24.05.2017 | |
| 3 | 15.05.2017 | 22.05.2017 | 24.05.2017 | |
| 4 | 22.05.2017 | 29.05.2017 | 07.06.2017 | |
| 5 | 29.05.2017 | 06.06.2017 | 07.06.2017 | |
| 6 | 05.06.2017 | 12.06.2017 | 21.06.2017 | |
| 7 | 12.06.2017 | 19.06.2017 | 21.06.2017 | |
| 8 | 19.06.2017 | 26.06.2017 | 05.07.2017 | |
| 9 | 26.06.2017 | 03.07.2017 | 05.07.2017 | |
| 10 | 03.07.2017 | 10.07.2017 | 19.07.2017 | |
| 11 | 10.07.2017 | 17.07.2017 | 19.07.2017 | PDF (for your solution of problem 1, you can edit this file in Ipe) |
| 12 | 17.07.2017 | 19.07.2017 | 19.07.2017 |
Supplementary Material
locally accessible material
Textbooks
The lecture does not follow a specific text book. The following text books contain general information on graph algorithms.- T. Nishizeki, N. Chiba: "Planar Graphs: Theory and Algorithms". Dover Pubn Inc, 2008
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: "Introduction to Algorithms." MIT Press, 2009
- K. Thulasiraman, M. N. S. Swamy: "Graphs: Theory and Algorithms". John Wiley and Sons, Inc. 1992
- Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin: "Network Flows: Theory, Algorithms, and Applications". Prentice Hall, 1993
- Reinhard Diestel: "Graph Theory". Springer, 2010