University of Konstanz
Prof. Dr. Ulrik Brandes

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

Please register for this course in the StudIS and LSF.


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 24.04.2017 08.05.2017 10.05.2017 PDF
2 08.05.2017 15.05.2017 24.05.2017 PDF
3 15.05.2017 22.05.2017 24.05.2017 PDF
4 22.05.2017 29.05.2017 07.06.2017 PDF
5 29.05.2017 06.06.2017 07.06.2017 PDF
6 05.06.2017 12.06.2017 21.06.2017 PDF
7 12.06.2017 19.06.2017 21.06.2017 PDF
8 19.06.2017 26.06.2017 05.07.2017 PDF
9 26.06.2017 03.07.2017 05.07.2017 PDF
10 03.07.2017 10.07.2017 19.07.2017 PDF
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 PDF

Supplementary Material

locally accessible material


The lecture does not follow a specific text book. The following text books contain general information on graph algorithms.

Further Information