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

2023S, VU, 3.0h, 4.5EC
TUWEL

Merkmale

  • Semesterwochenstunden: 3.0
  • ECTS: 4.5
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Präsenz

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

  • grundlegende Konzepte, Strukturen, Qualitätskriterien und Problemdefinitionen des Graphenzeichnens zu erklären. 
  • die vorgestellten Algorithmen und Layoutstile zu erklären, zu bewerten und zu analysieren
  • für verwandte Problemstellungen angemessene Algorithmen und Layoutstile auszuwählen und anzupassen
  • unbekannte angewandte und theoretische Probleme des Graphenzeichnens eigenständig zu modellieren, zu analysieren, effiziente Lösungen zu entwerfen und diese ggf. zu implementieren 

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

Methoden

  • Definition, Entwurf und Analyse von Algorithmen und Layout-Qualitätskriterien 
  • Diskussion und formale Beweise algorithmischer, geometrischer und ästhetischer Eigenschaften 
  • Berechnen von Beispielen
  • Bearbeiten von Aufgaben des Graph Drawing Contests in Übungsgruppen
  • Lesen und Präsentieren von aktueller Fachliteratur

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

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.

 

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mi.14:00 - 16:0001.03.2023 - 28.06.2023Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.09:00 - 11:0007.03.2023 - 27.06.2023Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Di.09:00 - 11:0014.03.2023Seminarraum FAV 01 A (Seminarraum 183/2) Übungsgruppentreffen
Mi.14:30 - 16:0010.05.2023Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Mi.16:00 - 17:0028.06.2023Seminarraum FAV 01 A (Seminarraum 183/2) Übungsvorträge
Graph Drawing Algorithms - Einzeltermine
TagDatumZeitOrtBeschreibung
Mi.01.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.07.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.08.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.14.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Di.14.03.202309:00 - 11:00Seminarraum FAV 01 A (Seminarraum 183/2) Übungsgruppentreffen
Mi.15.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.21.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.22.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.28.03.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.29.03.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.18.04.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.19.04.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.25.04.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.26.04.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.02.05.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.03.05.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung
Di.09.05.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.10.05.202314:30 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Di.16.05.202309:00 - 11:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung/Übung
Mi.17.05.202314:00 - 16:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung/Übung

Leistungsnachweis

  • Entwurf und Implementierung bzw. Erstellung von Graphlayouts für den Graph Drawing Contest 2023 und Präsentation der Ergebnisse (Gruppenarbeit) oder (wahlweise)
  • Lesen und Präsentation eines aktuellen theoretischen Papers zu Graph Drawing
  • Präsentation und Diskussion des Lehrinhaltes in einer mündlichen Prüfung

Die mündliche Prüfung zählt zu 60% der Note, der Übungsteil zu 40%.

Prüfungen

TagZeitDatumOrtPrüfungsmodusAnmeldefristAnmeldungPrüfung
Fr.09:00 - 13:0005.07.2024 mündlich11.06.2024 11:00 - 02.07.2024 23:59in TISSGraph Drawing Algorithms -- oral exam
Di. - 24.09.2024mündlich11.06.2024 11:00 - 20.09.2024 23:59in TISSGraph Drawing Algorithms -- oral exam

LVA-Anmeldung

Von Bis Abmeldung bis
15.02.2023 00:00 08.03.2023 23:59 31.03.2023 23:59

Curricula

StudienkennzahlVerbindlichkeitSemesterAnm.Bed.Info
066 645 Data Science Gebundenes Wahlfach
066 926 Business Informatics Gebundenes Wahlfach
066 931 Logic and Computation Gebundenes Wahlfach
066 932 Visual Computing Gebundenes Wahlfach
066 937 Software Engineering & Internet Computing Gebundenes Wahlfach

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

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

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

Vorausgehende Lehrveranstaltungen

Vertiefende Lehrveranstaltungen

Sprache

Englisch