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

2023S, VU, 3.0h, 4.5EC
TUWEL

Properties

  • Semester hours: 3.0
  • Credits: 4.5
  • 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

Mode of examination

Immanent

Additional information

Due to an increase of the ECTS points the VU Graph Drawing Algorithms will take place with the new TISS ID 192.141 from 2023S and no longer as 192.053.

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

25 h lecture attendance
25 h follow-up of lecture material and exam preparation
62 h programming project or theory paper work
0,5 h oral exam
------
112,5 h total

Teaching Mode

Currently the course is planned to be held in presence.

Lecture Dates

We will have about 15 lecture units taking place in the reserved time slots on Tue or Wed; the actual dates will be announces in the first lecture and here on this page.

 

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Wed14:00 - 16:0001.03.2023 - 28.06.2023Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue09:00 - 11:0007.03.2023 - 27.06.2023Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue09:00 - 11:0014.03.2023Seminarraum FAV 01 A (Seminarraum 183/2) meeting of exercise groups
Wed14:30 - 16:0010.05.2023Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Wed16:00 - 17:0028.06.2023Seminarraum FAV 01 A (Seminarraum 183/2) Exercise presentations
Graph Drawing Algorithms - Single appointments
DayDateTimeLocationDescription
Wed01.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue07.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed08.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue14.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Tue14.03.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) meeting of exercise groups
Wed15.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue21.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed22.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue28.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed29.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue18.04.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed19.04.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue25.04.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed26.04.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue02.05.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed03.05.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise
Tue09.05.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed10.05.202314:30 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Tue16.05.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Lecture/Exercise
Wed17.05.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture/Exercise

Examination modalities

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

The oral exam counts for 60% of the grade, the exercise coursework for 40%.

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Fri09:00 - 13:0005.07.2024 oral11.06.2024 11:00 - 02.07.2024 23:59TISSGraph Drawing Algorithms -- oral exam
Tue - 24.09.2024oral11.06.2024 11:00 - 20.09.2024 23:59TISSGraph Drawing Algorithms -- oral exam

Course registration

Begin End Deregistration end
15.02.2023 00:00 08.03.2023 23:59 31.03.2023 23:59

Curricula

Study CodeObligationSemesterPrecon.Info
066 645 Data Science Mandatory elective
066 926 Business Informatics Mandatory elective
066 931 Logic and Computation Mandatory elective
066 932 Visual Computing Mandatory elective
066 937 Software Engineering & Internet Computing Mandatory elective

Literature

No lecture notes are available.

Previous knowledge

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

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

Preceding courses

Continuative courses

Language

English