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).
Die erste Vorlesungseinheit findet am 12.03.2024 statt.
Die Einführung in den verpflichtenden Übungsbetrieb findet am 19.03.2024 statt.
Wegen einer Erhöhung der ECTS findet die VU Graph Drawing Algorithms ab 2023S unter dieser neuen TISS ID 192.141 statt und nicht mehr als 192.053.
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
25 h Vorlesungsbesuch
25 h Vorlesungsnachbereitung und Prüfungsvorbereitung
62 h Programmierprojekt oder theoretische Arbeit
0,5 h Mündliche Prüfung
------
112,5 h gesamt
Lehrmodus
Aktuell wird die LVA im Präsenzbetrieb geplant.
Termine
Es wird ca. 15 Vorlesungstermine zu den reservierten Zeiten geben; die konkreten Tage werden in der ersten Vorlesung und hier bekannt gegeben.
Erforderlich: gute Grundkenntnisse zu Algorithmen und Datenstrukturen, insbesondere Graphenalgorithmen (z.B. 186.866).
Hilfreich: vertiefende Kenntnisse in Algorithmik (z.B. 186.814, 192.133, 192.018) und Kenntnisse in Visualisierung (z.B. 186.827, 186.833, 188.305)
