University of Konstanz
Algorithmik
Prof. Dr. Ulrik Brandes

Algorithms for Planar Graphs (Summer 2015)

+++ News +++

registration to the LSF should now be possible

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: 13th of July 2015 in PZ 1006
2nd date: 29th of September 2015 in PZ 1006, please sign into the list in PZ 1002

Please register for this course in the StudIS and LSF.

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.

We will return the corrected and scored assignments fortnightly in the tutorial.

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 13.04.2015 20.04.2015 29.04.2015 PDF
2 20.04.2015 27.04.2015 29.04.2015 PDF
3 27.04.2015 04.05.2015 13.05.2015 PDF and the solution for Exercise 1 (c)
4 04.05.2015 11.05.2015 13.05.2015 PDF
5 11.05.2015 18.05.2015 03.06.2015 (!) PDF
6 18.05.2015 01.06.2015 03.06.2015 (!) PDF
7 01.06.2015 08.06.2015 17.06.2015 PDF (Update in the Hint of Problem 1)
8 08.06.2015 15.06.2015 17.06.2015 PDF
9 15.06.2015 22.06.2015 24.06.2015 (!) PDF (You can edit this file with Ipe if you are lazy...)
10 22.06.2015 29.06.2015 08.07.2015 PDF (UPDATE: of course the graph in Problem two has to be planar...)
11 29.06.2015 06.07.2015 08.07.2015 PDF

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.

Further Information