TU Wien:Graph Drawing Algorithms VU (Nöllenburg)

Daten

Zuordnungen

Masterstudium Data Science	Modul BDHPC/EX - Big Data and High Performance Computing - Extension (Gebundenes Wahlfach)
Masterstudium Business Informatics	Modul ISE/EXT - Information Systems Engineering Extension (Gebundenes Wahlfach)
Masterstudium Logic and Computation	Modul Algorithmics and Complexity (Gebundenes Wahlfach)
Masterstudium Visual Computing	Modul Advanced Visualization (Gebundenes Wahlfach)
Masterstudium Software Engineering & Internet Computing	Modul Algorithmik (Gebundenes Wahlfach)

Inhalt

Grob zusammengefasst geht es in der LVA darum, Techniken und Algorithmen zu beleuchten, die eine für Menschen gut lesbare Repräsentation verschiedener Graphen zum Ziel haben. Zum Beispiel die Berechnung einer planaren Zeichnung eines planaren Graphen, optimierung der Winkel der Kanten bzw diskrete auswahl möglicher WInkel (zB bei U-Bahn-Plänen), Minimirung der Kreuzungen bei nicht-planaren graphen, hierarchische Darstellungen (Flowcharts), Zeichnung auf Ebenen (zB Sugiyama Framework), Kreis-Graphen, Zeichnung auf diskreten Koordinaten (zusätzlich: Minimierung der benötigten Fläche)...

Das Fach ist sowohl für Logikinteressierte, als auch für Leute die sich mit Computer Graphics beschäftigen interessant.

Der Fokus liegt auf der mathematischen Theorie. Es werden einige Algorithmen besprochen, deren Eigenschaften dann minuziös diskutiert und bewiesen werden. Zusätzlich werden generelle Eigenschaften von Graphen und ihrere Zeichnungen teilweise über gleich mehrere Lemmas und Beweisschritte hergeleitet. Es wird zwar regelmäßig erwähnt, dass einzelne Gesichtpunkte in der Praxis wichtig sind, aber der LVA-Stoff ist fest in der (trockenen) Theorie verankert.

Ablauf

Wöchentliche Vorlesung, manchmal auch zweimal wöchentlich. Es gibt eine große Übung die über das ganze Semester geht, also keine Aufgabenblätter oder Zwischentests. Man kann wählen, ob man eine Gruppenarbeit (Programmierung oder Visualisierung) bearbeitet, oder alleine arbeitet (Paper Präsentation). Am Ende gibt es eine mündliche Prüfung.

Benötigte/Empfehlenswerte Vorkenntnisse

Mathematik VOs aus dem Bachelor

Algorithmen und Datenstrukturen

Oder allgemein: Basiswissen zur Graphentheorie, vertiefendes Wissen zb via andere Masterfächer ist bei manchen Themen vorteilhaft.

Vortrag

Der Professor macht viele Notizen auf den Folien die dann später über TUWEL verfügbar gemacht werden. Es gibt kein Skriptum, sondern nur die Folien und zusätzliches Lesematerial/Quellen auf die sich die VO stützt. Manchmal ist die Vorlesung etwas interaktiv (z.B. kleine Diskussionen oder Punkte nennen die einem einfallen). Generell ist der Stil sehr locker, und die Algorithmen und Beweise werden schrittartig erarbeitet, das jedoch in raschem Tempo. Es werden sehr viele Beweise geführt, wovon manche ziemlich lang sind. Die Stoffmenge in den Einheiten ist detailliert und viel, und lässt wenig Verschnaufpausen zu wenn man kontinuierlich folgen möchte.

Übungen

Es gibt eine große Übung die über das ganze Semester geht, wobei man drei Auswahlmöglichkeiten hat. Zwei davon sind Gruppenarbeiten: entweder eine Programmieraufgabe, bei der man die Anzahl de Kreuzungen bei arbiträren Input-Graphen minimieren muss (Optimization), oder Kreativ-Aufgabe, bei welcher für einen Inputgraphen mit klar definierten Daten ein Poster entworfen werden muss, der die Informationen visuell ansprechend darstellt, wobei auch Informationen weggelassen oder hinzugefügt werden dürfen (Visualization). Entscheidet man sich für die Einzelaufgabe (Seed Paper), muss man ein vorgegebenes Thema wählen (zB Crossing-Bundling, Vertex Splitting...) und erhält danach ein Research-Paper zugewiesen. Man muss die Ergebisse des Papers präsentieren (eventuell under Berücksichtigung von Follow-ups, aufbauende Forschung oder ähnlichen Projekte). Die Deadlines sind jeweils der Tag der Präsentation, die immer in den letzten 2 Wochen des Semesters stattfindet (Angefangen mit Seed Paper Studis, gefolgt von Visualization Gruppen und abschließend die Optimization Gruppen).

Programmieraufgabe: Die Programmieraufgaben (Optimieren oder Visualisieren) stammen von der jährlichen Graph Drawing Competition (stand 2024S). Die Übungsabgaben werden dort für die beiden Kategorien eingereicht. In den vergangenen Jahren gab es so ca. 12 Teilnehmer unterschiedlicher Unis und die TU hat bei der kreativen Aufgabe häufig recht gut abgeschnitten.

2024S: Die Gruppen waren zu viert und es wurde ein Assistent pro Thema (kreativ oder optimieren) für die Gruppen als Betreuer vergeben. Während des Semesters gab es drei Milestone Meetings in Präsenz mit dem Betreuer wo der Fortschritt präsentiert und diskutiert wird. Die Meetings liefen recht entspannt ab, also keine Prüfungssituation. Jedoch gab es definitiv die Erwartungshaltung, dass von Meeting zu Meeting vozeigbarer Fortschritt existiert, sowie die Kritikpunkte vom letzten Meeting irgendwie behandelt/addressiert wurden. Es war immer gut wenn man eine handvoll (zur Not hässlicher) PowerPoint Folien hat, wo man schnell zeigen kann was man die letzten Wochen gemacht hat, vor allem wenn man zu was bestimmtem Feedback haben möchte. Da das Institut offensichtlich daran interessiert ist, beim Wettbewerb erfolgreich zu sein, sind die Meetings recht "konstruktiv" angelegt. Der Betreuer hat zumindest bei uns versucht seine eigenen Kritikpunkte mit uns zu lösen, und hat aktiv Ideen eingebracht bzw unsere diskutiert. Nachdem die VO mit den Übungsaufgaben zwar thematisch aber inhaltlich nur tagential zu tun hat, findet hier der notwendige Know-How Austausch statt.

Prüfung, Benotung

Die Übung trägt 40%, die mündliche Prüfung 60% zur Gesamtnote bei.

Die Benotung ist absolut fair. Die Prüfung bestand mehr aus einem 20-Minütigen Gespräch bei dem man selbst ziemlich viel in eine Richtung lenken konnte. Gefragt wurde dabei alles Mögliche von den Vorlesungsfolien (auch aus der ersten und letzten Einheit!), aber es wurde nicht sehr in die Tiefe gegangen. Der Professor legte dabei aber auch Wert auf Laufzeiten und obere/untere Schranken (z.B. Area Bounds), die sollte man sich also auch einprägen. Ansonsten wurde zwar nach Beweisen gefragt, aber hier hat es absolut gereicht eine kleine Skizze zu beschreiben. Es ging definitiv eher um Verständnis als ums auswendig Lernen. Meine Fragen:

• Was ist ein Graph? Welche Drawing Conventions gibt es, zwei Beispiele nennen.
• Hier habe ich dann das Sugiyama Framework genannt und sollte es dann in mehr Detail beschreiben:
  • Die einzelnen Schritte aufzählen und jeweils die in der VO besprochenen Heuristiken und Methoden beschreiben
  • Laufzeiten der Heuristiken
• SP-Graphs: Rekursive Definition, Drawing Area Bounds, Beweisskizze (planarität und azyklisch)
• Generelle Fragen zu planaren Graphen (Eigenschaften, Algorithmen nennen die wir in der VO gesehen haben)

Insgesamt war die Prüfung ziemlich genau 20 Minuten lang und absolut ohne übermäßigem Aufwand schaffbar.

Hatte Ende September Prüfung und meine Erfahrung war da sehr ählich. Die Prüfung war mega entspannt und fair und nachdem sie ja nur 20 Minuten dauerte, wurde auch nicht so extrem ins Detail gegangen. Ich hab folgende Fragen bekommen:

• Graph Drawing Problem beschreiben, was sind Drawing Conventions, Aesthetic Criteria und Constraints, nenne jeweils Beispiele
• Ich habe uniform edge lengths erwähnt und wurde gefragt ob ich eine Methode kenne bei der das vorkam, ich habe Metro Maps erwähnt
  • Sollte dann das Metro Maps Problem genauer beschreiben und sagen welche Kriterien es dabei gibt
  • habe auch kurz die einzelnen Schematisations zusammengefasst
  • wurde noch genauer gefragt was octolinearität ist
• Von octolinearität kamen wir zu orthogonal graph drawing
  • STM framework beschreiben
  • Flow network für bend minimization genauer beschreiben mit skizze und bounds, euler formel wollten sie beim Beweis der Gültigkeit des Netzwerks auch hörn
  • Kurz erklären wie das mit der area minimization funktionieren würde und sagen, was die complexity davon ist
  • beweis für np completeness von area minimization ganz grob beschreiben

2024S: Hatte Prüfung Ende September mit einem Kollgegen. Jeder hatte einen 20 Minuten Slot. Es waren Prof. Nöllenburg ein Assistent anwesend. Die Fragen hat nur Nöllenburg gestellt und der Assistent hat Protokoll geführt. Nach der Eingangsfrage hat das Gespräch recht natülich seinen Lauf genommen und man konnte die Themen auch lenken. Die Fragen waren recht weit gestellt, so dass man auch etwas ausholen konnte. Er wollte Eigenschaften/Grenzen von Algorithemn präzise hören, aber für Beweise haben Verständnis und eine inhaltliche Erklärung genügt. Es gab Papier und Stift, wenn man was aufzeichnen wollte. Ein Kollege der vor uns dran war hat gemeint, wenn man was nicht weiß wird nicht nachgebohrt, sonder das Thema gewechselt, gibt aber natürlich Abzüge. Prüfung kann auf Deutsch oder English absolviert werden (wobei durch die Fachworte aus der englischen VO eher Denglisch draus wird). Die beiden haben sich nach der Prüfung für 2-3 Minuten beraten und einen dann nochmal für die Note reingeholt.

• Graph Drawing Problem erklären (inklusive was ist ein Graph) und die drei Constraints/Conventions mit Beispielen
• Planare Graphen zeichnen: ich durfte mir einen Algorithmus aussuchen und habe Schnyder-Realizer genommen
  • Baryzentrische Koordinaten + Repräsentation (mit dem Beweis für Planarität)
  • Schnyder Labeling mit Definition und Ablauf (Edge-Contraction)
  • Schnyder Realizer und Grenzen für Fläche & Laufzeit (mit Begründung)
• SP-Graphen
  • Rekursive Definition, Decomposition Tree und Eigenschaften mit Beweis für Planarität/Azyklus
  • Exponentiellen Upper-Bound für Flächeninhalt bei Zeichnungen ohne Umordnung erklären: Hier hab ich die Struktur vom Graphen gezeichnet und sehr grob die Form vom Bounding-Triangle. Es hat gereicht dass ich den exoponentiellen Flächenzuwachs wie folgt zu begründen: "Da die beiden Source-Nodes zum Sink-Node mit geraden Linien verbunden werden müssen, muss das nächste Bounding-Triangle eine bestimmte Mindestgröße haben. Man kann dann zeigen, dass aufgrund geometische Gegebenheiten dieses Dreieck zumindest viermal größer sein muss als das umschlossene."
  • Alogrithmus für Right-Pushed Drawings erklären und die Grenze für den Flächeninhalt beweisen (hier wieder recht viel aufgezeichnet)

Dauer der Zeugnisausstellung

~ Zwei Wochen

Semester	Prüfung	Zeugnis	Dauer
WS10	04.02.2011	18.02.2011	2 Wochen
WS11	03.02.2011	20.03.2011	6,5 Wochen
SS24	24.09.2024	24.09.2024	selber Tag

Zeitaufwand

Variiert wahrscheinlich stark je nach Semester. Man kann sich schon ganz schön in die Übung vertiefen, aber insgesamt war der Zeitaufwand OK.

2024S: Zeitaufwand ist hoch und für 4,5ECTS selbst für TU-Verhältnisse fast frech. Die Übung verschlingt viel Zeit nachdem es keine 0815-Aufgabe ist die jeder gleich löst, sondern projektartig unterschiedliche Ideen erarbeitet und ausprobiert werden müssen. Die Milestone-Meeting sind sehr hilfreich (und notwendig) aber benötigen zusätzliche Vorbereitungszeit. Auf die Qualität der Abschlusspräsentation wird ebenfalls Augenmerk gelegt, weshalb dort auch Arbeit hineinfließt. Der Vorlesungsstoff ist extrem umfangreich (>1000 Folien) und eher auf der komplizierten Seite. Aus Erfahrungsberichten geht hervor, dass die Prüfungsgespräche in der Regel keine tiefsten Details verlangen, aber man alles zumindest erklären können muss. Man kann daher beim Lernen kaum was komplett auslassen, und muss sich einiges was man in der VO nicht verstanden hat oder wieder vergessen hat selbst zusammenreimen. Der Lernaufwand ist nicht zu unterschätzen (in den Ferien ca. 11 Tage).

Unterlagen

Annotierte Folien über TUWEL

Teilweise weiterführende Infos zu ausgewählten Themen als PDF (auch über TUWEL)

Manche der empfohlenen Bücher sind online abrufbar; sonst in der Bibliothek

Online Quizzes zur Selbstüberprüfung in TUWEL

Tipps

Es gibt gute Aufzeichnungen zu den Vorlesungen; Anwesenheit ist also nicht unbedingt notwendig

2024S: Keine Aufzeichnungen, und mangels Skriptum sind die Folien trotz Skizzen alleine nicht immer wahnsinnig aufschlussreich. Man musste zur Mehrheit der VOs gehen, damit man nacher sinnvoll lernen kann.

Highlights / Lob

• Gute Vorlesung (sogar mit Interaktivität zeitweise) und der Stoff wird mit Skizzen laufen erarbeitet
• Engagierte Übungsbetreuer, und mit dem Wettbewerb hat man das Gefühl, auf was hinzuarbeiten, dass sich nacher sogar wer anschaut

Verbesserungsvorschläge / Kritik

• Evtl. könnte man bei den Folien eine condensed Version einfügen bei denen die Zwischenfolien rausgenommen wurden. Das würde beim Lernen helfen.
• Zeitaufwand und notwendige Abreitsleistung (siehe oben)

Materialien

Neues Material hinzufügen

Z

• Zusammenfassung 2024S
• Zusammenfassung GDA 2024S.pdf (details)