Algorithms for Planar Graphs (Summer 2016)
+++ News +++ |
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 11:45-13:15 (M 630) |
Tutorial | Wed 15:15-16:45 - fortnightly (F 429) |
Exams | 1st date: 18th of July 2016 in PZ 1006 2nd date: 4th of October 2016 in PZ 1006 |
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 11:30 (AM).
- The assignments have to be delivered in written form either in English or German.
- You have to submit them electronically to pg_u_s16@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 | 11.04.2016 | 18.04.2016 | 20.04.2016 | |
2 | 18.04.2016 | 25.04.2016 | 04.05.2016 | |
3 | 25.04.2016 | 02.05.2016 | 04.05.2016 | PDF (Example solution for question 2) |
4 | 02.05.2016 | 09.05.2016 | 18.05.2016 | |
5 | 09.05.2016 | 16.05.2016 | 18.05.2016 | |
6 | 23.05.2016 | 30.05.2016 | 08.06.2016 (!) | |
7 | 30.05.2016 | 06.06.2016 | 08.06.2016 (!) | |
8 | 06.06.2016 | 13.06.2016 | 22.06.2016 | |
9 | 13.06.2016 | 20.06.2016 | 22.06.2016 | |
10 | 20.06.2016 | 27.06.2016 | 06.07.2016 | PDF (For problem 2, you can edit this file in Ipe) |
11 | 27.06.2016 | 04.07.2016 | 06.07.2016 | |
12 | 05.07.2016 | 11.07.2016 | 13.07.2016 |
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