University of Konstanz
Algorithmik
Prof. Dr. Ulrik Brandes

Graph Drawing (SS 2015)

+++ Announcements +++

The second date for oral exams is Monday, September 28th (room PZ 1005). Please register in Studis and contact us via the email-alias to fix a time slot.

Layout algorithms for graphs form the basis of effective and efficient visualization of networks.

Thus, automatic graph drawing is important in core areas of computer science like data bases, software engineering, VLSI and network design, and visual user interfaces. It is also relevant in other application areas, for example, in engineering, chemistry and biology, and social or political science.

Various algorithmic methods for automatic graph drawing will be treated, for instance, force-directed or flow-based methods.

General Information

Lecture (M. Mader)
Algorithmics Group (U. Brandes)
Tue 11:45–13:15 (M 901)
Thu 11:45–13.15 (M 701)
Tutorial (Barbara Pampel) Wed 13:30–15:00 (M 630)
 
oral exams first date: Mon, July 27, 2015 (PZ1005)
second date: Mon, September 28, 2015 (PZ1005)

Please use gd_s15@inf.uni-konstanz.de for any inquiries or feedback.

Assignments

Theoretical Assignments

The theoretical assignments are made available on this webpage on Thursday. The solutions are usually due in written form until Thursday the week after handout at 12 a.m.. You can choose to either return your handwritten solution at the beginning of the Thursday lecture, or to submit them electronically in one PDF file to: gd_s15@inf.uni-konstanz.de .

In the latter case, please follow the naming schema aXX_name1_name2.pdf, where XX indicates the number of the assignment. We will return the corrected and scored assignments in the tutorial.

Solutions can be written in English or German.

Practical Assignments

The practical assignments have to be implemented in Java.

We suggest to use the development environment Eclipse (download). Feel free to use any other editor/IDE as long as you submit in the correct way.

The data structures and visualization methods we will be using are provided by the yFiles library (API), contained in the project data for the first practical assignment. The library license is restricted to academic purposes within the algorithmics group. You are neither allowed to distribute the library, nor to use it for projects outside the scope of this lecture.

The submission of practical assignments will be via svn. The base directory is https://svn.uni-konstanz.de/algo/gd_s15/. Each group will have access to only one sub-package and the material package. Use your university login firstname.lastname with the corresponding password for access.
Further requirements:

Examination Admittance

The assignments are returned and discussed during the tutorials. 50 percent of the total score of the assignments, regular attendance at the tutorials, and the presentation of at least one of your solutions are necessary to be admitted to the final exam.

You are permitted and encouraged to work in groups of two.

Downloads

No. Posted Due Date Tutorial Download
0 4/16 4/23 4/29 warm-up (a00)
1 4/23 4/30 5/6 a01
2 4/30 5/7 5/13 a02
3 5/7 5/14 5/20 a03
4 5/15 5/21 5/27 a04
5 5/21 5/28 6/3 a05
6 5/28 6/4 6/10 a06
7 6/4 6/11 6/17 a07
8 6/11 6/18 6/24 a08
9 6/18 6/25 7/1 a09
10 6/25 7/2 7/8 a10 (including solution for 4c)
11 7/2 7/9 7/15 a11
11 7/9 7/15 7/15 (bonus) a12

Lecture Notes (local access only)

The lecture will be based on lecture notes (in German) from the same course in 2007.

Textbooks

Further Information