# 192.053 Graph Drawing Algorithms This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_20",{id:"j_id_20",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_22",{id:"j_id_22",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2022S 2021S 2020S 2019S 2018S

2022S, VU, 2.0h, 3.0EC

## Properties

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

## Learning outcomes

After successful completion of the course, students are able to

• explain fundamental concepts, structures, quality criteria, and problem definitions in graph drawing
• explain, assess, and analyze the discussed algorithms and layout styles
• select and adapt appropriate algorithms and layout styles to related problems
• model and analyze unknown applied or theoretical graph drawing problems and develop and possibly implement efficient solutions independently

## 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.

## Teaching methods

• Definition, design and analysis of algorithms and layout quality measures
• Discussion and formal proofs of algorithmic, geometric, and aesthetic properties
• Solving and discussing examples
• Solving of tasks from the Graph Drawing Contest in small groups
• Reading and presenting state-of-the-art literature

Immanent

## 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

20 h lecture attendance
24 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

### Teaching Mode

Currently the course is planned to be held in presence. In case the current situation ot the COVID regulations of TU Wien prohibit this, we will switch to distance teaching. Video recordings of previous terms are available, but course material may change. The exam will cover the course material of the current term.

## Course dates

DayTimeDateLocationDescription
Tue09:00 - 11:0001.03.2022 - 28.06.2022Seminarraum FAV 05 (Seminarraum 186) Lecture
Wed10:00 - 12:0030.03.2022Seminarraum FAV EG C (Seminarraum Gödel) Ipe Tutorial
Tue09:00 - 12:0012.07.2022Seminarraum FAV 05 (Seminarraum 186) oral exams
Graph Drawing Algorithms - Single appointments
DayDateTimeLocationDescription
Tue01.03.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue08.03.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue15.03.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue22.03.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue29.03.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Wed30.03.202210:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Ipe Tutorial
Tue05.04.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue26.04.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue03.05.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue10.05.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue17.05.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue24.05.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue31.05.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue14.06.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue21.06.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue28.06.202209:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Tue12.07.202209:00 - 12:00Seminarraum FAV 05 (Seminarraum 186) oral exams

## Examination modalities

• Either design and implement/create graph layouts for the graph drawing contest 2022 and present the results (group work) or
• present a state-of-the-art research paper
• Present and discuss the course content in an oral exam

The oral exam counts for 70% of the grade, the exercise coursework for 30%.

## Course registration

Begin End Deregistration end
14.02.2022 00:00 09.03.2022 23:59 28.06.2022 23:59

## 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)

English