192.053 Graph Drawing Algorithms
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2019S, VU, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

Die Studierenden erwerben ein systematisches Verständnis von Visualisierungsstilen, algorithmischen Fragestellungen und algorithmischen Lösungsansätzen im Bereich des Graphenzeichnens, das auf dem bestehenden Wissen zu Algorithmen und Datenstrukturen aufbaut und an das Anwendungsgebiet der Informationsvisualisierung anknüpft. Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen und grundlegende Problemdefinitionen aus der Vorlesung erklären;
  • Algorithmen zum Graphenzeichnen formal und intuitiv beschreiben, mathematisch präzise analysieren und ihre Eigenschaften beweisen;
  • Graphenvisualisierungswerkzeuge und -bibliotheken anwenden und damit eigene Zeichnungen erstellen;
  • auswählen, welche Algorithmen zur Lösung eines gegebenen Graphenvisualisierungsproblems geeignet sind und diese ggf. einer konkreten Problemstellung anpassen;
  • unbekannte Graphenvisualisierungsprobleme analysieren, auf den algorithmischen Kern reduzieren und daraus ein abstraktes Modell erstellen; 
  • auf Basis der in der Vorlesung erlernten Konzepte und Techniken eigene Lösungen in diesem Modell entwerfen, analysieren und die Eigenschaften beweisen.

Inhalt der Lehrveranstaltung

Graph Drawing oder Graphenzeichnen beschäftigt sich mit der geometrischen Repräsentation von Graphen in der Ebene und bildet den algorithmischen Kern der Netzwerkvisualisierung. Graphenzeichnen ist motiviert durch Anwendungen, in denen relationale Daten als Graph modelliert und vom Menschen visuell analysiert und exploriert werden. Beispiele solcher Anwendungsfelder sind Data Science, Sozialwissenschaften, Web Computing, Informationssysteme, Biologie, Geowissenschaften, Business Intelligence, Informationssicherheit und Software Engineering. Das Gebiet Graph Drawing kombiniert Aspekte aus Algorithmik, Graphentheorie, algorithmischer Geometrie und Visualisierung.

In dieser Lehrveranstaltung definieren wir gängige ästhetische Qualitätskriterien und Layoutstile im Graphenzeichnen. Anschließend betrachten wir die zugehörigen Optimierungsprobleme aus einer formalen, algorithmischen Perspektive. Es werden einige der verbreitetsten Graph-Drawing-Algorithmen behandelt, die von der Visualisierung allgemeiner Graphen hin zu spezifischen Algorithmen für bestimmte Graphklassen (z.B. planare Graphen und Bäume) reichen. Die betrachteten Layout-Algorithmen nutzen bekannte Prinzipien des Algorithmenentwurfs wie Divide-and-Conquer, inkrementelle Algorithmen und Netzwerkflussmodelle. Es werden sowohl praktische als auch theoretische Aspekte des Graphenzeichnen behandelt (z.B. Komplexitätsanalysen von Layoutproblemen und Algorithmen).

Weitere Informationen

Neben den wöchentlichen Vorlesungseinheiten wird es einen begleitenden Übungsteil geben, in dem die Studierenden die Wahl haben entweder ein praktisches Programmierprojekt in einer Gruppe von 2-3 Studierenden zu bearbeiten und am Ende zu präsentieren (inkl. Möglichkeit der Teilnahme am jährlichen Graph Drawing Contest) oder sich eine aktuelle theoretische Forschungsarbeit zu erarbeiten und in einem Vortrag am Ende des Semesters zu präsentieren.

ECTS-Breakdown

24 h Vorlesungsbesuch
20 h Vorlesungsnachbereitung und Prüfungsvorbereitung
30 h Programmierprojekt oder Vortragsvorbereitung
  1 h Mündliche Prüfung
------
75 h gesamt 

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.09:00 - 11:0005.03.2019 - 25.06.2019Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.09:00 - 14:0009.07.2019Seminarraum FAV 05 (Seminarraum 186) Präsentationstermin
Graph Drawing Algorithms - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.05.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.12.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.19.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.26.03.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.02.04.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.09.04.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.30.04.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.07.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.14.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.21.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.28.05.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.04.06.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.18.06.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.25.06.201909:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Di.09.07.201909:00 - 14:00Seminarraum FAV 05 (Seminarraum 186) Präsentationstermin

Leistungsnachweis

Die Gesamtnote setzt sich zusammen aus einer mündlichen Prüfung (70%) und der Leistung im Übungsteil (30%).

Prüfungen

TagZeitDatumOrtPrüfungsmodusAnmeldefristAnmeldungPrüfung
Fr.09:00 - 10:1017.07.2020 HC 04 11mündlich01.06.2020 00:00 - 14.07.2020 23:55in TISSGraph Drawing Algorithms oral exam
Fr.10:20 - 11:3017.07.2020 HC 04 11mündlich01.06.2020 00:00 - 14.07.2020 23:55in TISSGraph Drawing Algorithms oral exam
Fr.11:40 - 13:0017.07.2020 HC 04 11mündlich01.06.2020 00:00 - 14.07.2020 23:55in TISSGraph Drawing Algorithms oral exam
Mo.09:00 - 10:1028.09.2020 HC 04 11mündlich26.05.2020 00:00 - 24.09.2020 23:55in TISSGraph Drawing Algorithms oral exam
Mo.10:20 - 11:3028.09.2020 HC 04 11mündlich26.05.2020 00:00 - 24.09.2020 23:55in TISSGraph Drawing Algorithms oral exam
Mo.11:40 - 12:5028.09.2020 HC 04 11mündlich26.05.2020 00:00 - 24.09.2020 23:55in TISSGraph Drawing Algorithms oral exam

LVA-Anmeldung

Von Bis Abmeldung bis
19.02.2019 00:00 19.03.2019 23:59 25.06.2019 23:59

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

Erforderlich: gute Grundkenntnisse zu Algorithmen und Datenstrukturen, insbesondere Graphenalgorithmen (z.B. 186.813, 186.815, 186.866). 

Hilfreich: vertiefende Kenntnisse in Algorithmik (z.B. 186.814, 186.122) und Kenntnisse in Visualisierung (z.B. 186.827, 186.833, 188.305)

Vorausgehende Lehrveranstaltungen

Vertiefende Lehrveranstaltungen

Sprache

Englisch