192.053 Graph Drawing Algorithms
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2019S, VU, 2.0h, 3.0EC

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Aim of course

Students acquire a systematic understanding of visualization styles, algorithmic layout problems, and algorithmic solutions in the area of graph drawing that connects to their existing knowledge on (graph) algorithms and data structures and to the application field information visualization. After successfully participating in the course students can

  • explain notions, structures, and fundamental problem definitions from the lectures;
  • describe graph drawing algorithms formally and intuitively, analyze them with mathematical precision, and prove their properties;
  • apply graph visualization tools and libraries to create graph layouts;
  • select which algorithms are suitable for a given graph visualization problem and adapt them to the given problem setting;
  • analyze unknown graph visualization problems, reduce them to their algorithmic core, and create an abstract problem model;
  • design own algorithmic solutions in that model, based on the concepts and techniques covered in the lecture, analyze these algorithms and prove their properties.

Subject of course

Graph drawing is concerned with the geometric representation of graphs in the plane and constitutes the algorithmic core of network visualization. Graph drawing is motivated by applications where it is crucial to visually analyze, explore, and interact with relational datasets. Examples of such application areas include data science, social sciences, Web computing, information systems, biology, geography, business intelligence, information security and software engineering. The research area graph drawing combines aspects of algorithmics, graph theory, computational geometry, and visualization.

In this course we define common aesthetic quality criteria and layout styles in graph drawing. Subsequently, we study the corresponding optimization problems from a formal, algorithmic perspective. We cover some of the most fundamental graph drawing algorithms, ranging from general-purpose algorithms to specific algorithms for certain graph classes (e.g., trees and planar graphs). The algorithms use known algorithm design principles such as divide-and-conquer, incremental constructions, and network flow models. The course covers both practical and theoretical aspects of graph drawing.

Additional information

In addition to the weekly lectures there is an accompanying exercise part, in which students can choose to either work on a practical programming project in a group of 2-3 students and present the results at the end of the course (incl. the option to participate in the annual graph drawing contest), or to read and understand a recent theoretical research paper and present it to the class at the end of the term.

ECTS-Breakdown

24 h lecture attendance
20 h follow-up of lecture material and exam preparation
30 h programming project or preparation of theory paper presentation
  1 h oral exam
------
75 h total

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Tue09:00 - 11:0005.03.2019 - 25.06.2019Seminarraum FAV 05 (Seminarraum 186) lecture
Tue09:00 - 14:0009.07.2019Seminarraum FAV 05 (Seminarraum 186) Student presentations
Graph Drawing Algorithms - Single appointments
DayDateTimeLocationDescription
Tue05.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue12.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue19.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue26.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue02.04.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue09.04.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue30.04.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue07.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue14.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue21.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue28.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue04.06.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue18.06.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue25.06.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) lecture
Tue09.07.201909:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Student presentations

Examination modalities

The course grade is composed of an oral exam (70%) and the performance in the exercise part (30%).

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Fri09:00 - 10:1017.07.2020 HC 04 11oral01.06.2020 00:00 - 14.07.2020 23:55TISSGraph Drawing Algorithms oral exam
Fri10:20 - 11:3017.07.2020 HC 04 11oral01.06.2020 00:00 - 14.07.2020 23:55TISSGraph Drawing Algorithms oral exam
Fri11:40 - 13:0017.07.2020 HC 04 11oral01.06.2020 00:00 - 14.07.2020 23:55TISSGraph Drawing Algorithms oral exam
Mon09:00 - 10:1028.09.2020 HC 04 11oral26.05.2020 00:00 - 24.09.2020 23:55TISSGraph Drawing Algorithms oral exam
Mon10:20 - 11:3028.09.2020 HC 04 11oral26.05.2020 00:00 - 24.09.2020 23:55TISSGraph Drawing Algorithms oral exam
Mon11:40 - 12:5028.09.2020 HC 04 11oral26.05.2020 00:00 - 24.09.2020 23:55TISSGraph Drawing Algorithms oral exam

Course registration

Begin End Deregistration end
19.02.2019 00:00 19.03.2019 23:59 25.06.2019 23:59

Curricula

Literature

No lecture notes are available.

Previous knowledge

Required: solid basic knowledge in algorithms and data structures, particularly graph algorithms (e.g. 186.813, 186.815, 186.866)

Optional: advanced knowledge in algorithmics (e.g. 186.814, 186.122) and basic knowledge in visualization (e.g. 186.827, 186.833, 188.305)

Preceding courses

Continuative courses

Language

English