Topic outline
-
Graph Drawing: Algorithms for the Visualization of GraphsThis course covers the most important algorithms to draw graphs. Methods from the course Algorithmische Graphentheorie (Algorithmic Graph Theory) such as divide and conquer, flow networks and integer programming will be used. We will become familiar with measures of quality of a graph drawing as well as algorithms that optimize these measures.
Our goal is to get an overview of graph visualization and familiarize with common tools in order to consolidate our knowledge about the modeling and solving of problems with the help of graphs and graph algorithms.
The language of this course will be English or German depending on whether there are non-German speakers participating or not.
Lectures: Friday, 10:15–11:45 in Seminarraum II, Computer Science Building (M2), starting on April 21.
No lectures on May 19 and June 30! Last lecture on July 21 in SE 8, Physics building.
Tutorials: Wednesday, 16:00–17:30 in SE 8, Physics Building (P1), starting on April 26.
Lecturers: Johannes Zink (lectures) and Oksana Firman (tutorials)
Assessment: Oral examination (one candidate each, approx. 20 minutes) at the end of the lecture period (precise date will be set during the semester).
If you achieve at least 50% of the points on the exercise sheets, you receive a 0.3 grade bonus on the final grade (provided you pass the oral exam).
Extend: 5 ECTS, 2+2 SWS
Prerequisites: Highly recommended: Algorithmische Graphentheorie (Algorithmic Graph Theory)
Target Audience: Master Computer Science, Master Mathematics, Master Computational Mathematics, etc.
Videos:
There will be no new videos. Videos in German from the course in 2021 by Jonathan Klawitter will be made available.
Registration
Please enroll into this WueCampus course room: use the rightmost item in the bar below the course title: "Mich in diesem Kurs einschreiben".For the assessment, you need to register in WueStudy; the registration is open from April 16 until July 15.Literature
- Peter Eades, Giuseppe Di Battista, Roberto Tamassia, Ionnis Tollis: "Graph Drawing: Algorithms for the Visualization of Graphs", Pearson 1999. (Available in the University Library)
- Roberto Tamassia (editor): "Handbook of Graph Drawing and Visualization", Taylor & Francis 2014. (Available in the University Library)
-
We will provide the slides and further literature for each lecture. Additionally, there are videos from last year as well as from 2020 (here).
Date (+ long slides) Topic (+ short slides)
Old Videos (German)
Exercise Sheet
Literature 21.04.2023
21.04.2023
Introduction Graph Visualization
Drawing Trees via Divide & Conquer
Introduction
Layered · HV · Radial
Link
[GD Ch 3.1 & 3.2] 28.04.2023
Force-Directed Drawing Algorithms and Tutte-Embeddings
Framework · Eades + FR · Variants · Tutte
Link
[DG Ch 4, GD Ch 10]
05.05.2023
[small update: 09.05.2023]
Straight-Line Drawing of Planar Graphs
via Canonical Order and Shift Method
Intro · Canonical Order · Shift Method
Link
[PGD Ch 4.2, dFPP90]
12.05.2023 Straight-Line Drawing of Planar Graphs via Schnyder Realizer
Barycentric Representation · Schnyder Woods · Schnyder Drawings
Link
[PGD Ch 4.3, Sch90]
26.05.2023 Upward Planar Drawings (incl. Series-Parallel Graphs)
Intro · Recognition · Series-Parallel
Link
[GD Ch 6] 02.06.2023
Orthogonal Graph Drawing via Network Flow
Intro · Orthogonal Representation · Orthgonal Drawing · NP-Hardness
Link
[GD Ch 5, PGD Ch 8, Tam87, Pat01, EFKSSW22]
-
There will be a new exercise sheet every week after the lecture (probably not for the last lecture). The deadline for each is the next lecture. Your submission will be graded and if you achieve at least 50% of points, you receive a 0.3 grade bonus on the final grade (provided you pass the exam).
We ask you to build groups of two and submit one solution per group. Please state the names of both group members on your submission. Digital submissions are appreciated. You may use the provided LaTeX Template. We accept submissions in German and English.
-
-
Article in Frankfurter Allgemeine Sonntagszeitung (in German) File
-
Stafanie Schramm, Bulletin 4/2009 File
-