University of Konstanz
Prof. Dr. Ulrik Brandes

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

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 11.04.2016 18.04.2016 20.04.2016 PDF
2 18.04.2016 25.04.2016 04.05.2016 PDF
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 PDF
5 09.05.2016 16.05.2016 18.05.2016 PDF
6 23.05.2016 30.05.2016 08.06.2016 (!) PDF
7 30.05.2016 06.06.2016 08.06.2016 (!) PDF
8 06.06.2016 13.06.2016 22.06.2016 PDF
9 13.06.2016 20.06.2016 22.06.2016 PDF
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 PDF
12 05.07.2016 11.07.2016 13.07.2016 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