Section: Seminar: Visualisierung von Graphen | WS22: Seminar Visualisierung von Graphen

Section outline

Umfang:	5 ECTS, 2 SWS
Zeit & Ort:	dienstags, 14:15–15:45 Uhr, Raum SE III (Informatikgebäude)
Voraussetzung:	Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmische Graphentheorie zum Einsatz, diese besucht zu haben ist deshalb sehr empfohlen. Die Vorlesung Visualisierung von Graphen gehört zu haben ist hilfreich, aber nicht erforderlich.
Zielgruppe:	Master Informatik (empfohlen), Bachelor Informatik
Dozenten:	Alexander Wolff und Boris Klemz

Wenn Sie am Seminar teilnehmen möchten, kommen Sie zum ersten Termin am Dienstag, den 18.10.2022, um 14:15 Uhr – dieser wie auch das gesamte Seminar wird in Präsenzform stattfinden (sofern es keine anderslautende Regelung gibt). An diesem Termin bitten wir um vollständige Anwesenheit, da wir den Ablauf des Seminars besprechen und die Themenverteilung festlegen. Die Liste der Themen finden Sie weiter unten auf dieser Seite. Diese werden je nach Teilnehmerzahl jeweils alleine oder zu zweit bearbeitet. Machen Sie sich schon vorab Gedanken, welche Themen Sie gerne bearbeiten würden.

Bitte schreiben Sie sich schon jetzt in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen wollen. Melden Sie sich dazu bei WueCampus an (das haben Sie wahrscheinlich schon getan) und klicken in der "sekundären Navigationsleiste" (der Bereich unter dem Kurstitel) auf "Mich in diesen Kurs einschreiben" beziehungsweise "Enrol me in this course".

Thema in diesem Semester: Graphenzeichnen

In diesem Semester deckt das Seminar einen weiten Bereich des Themenfelds Graphenzeichnen ab. Alle Themen basieren auf sehr aktuellen Forschungsergebnissen, die auf dem diesjährigen International Symposium on Graph Drawing & Network Visualization (GD 2022) vorgestellt wurden. Betrachtet werden dabei sowohl eher theoretische Erkenntnisse, als auch Erfahrungen aus der praktischen Anwendung zur Visualisierung von unterschiedlichsten Strukturen. Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmische Graphentheorie zum Einsatz. Die Vorlesung Visualisierung von Graphen gehört zu haben, ist hilfreich, aber nicht erforderlich. Manche Themen enthalten spannende offene Forschungsfragen. Wenn in der zweiten Hälfte des Seminars Zeit bleibt, kann daran gemeinsam geforscht werden. Dies kann auch zu Themen von Praktikas, sowie Abschlussarbeiten im Anschluss an das Seminar führen.


Titel	Autoren
Compatible Spanning Trees in Simple Drawings of K_n (🍭)	Aichholzer, Knorr, Mulzer, El Maalouly, Obenaus, Paul, Reddy, Vogtenhuber, Weinberger
Empty Triangles in Generalized Twisted Drawings of K_n (🍭)	García, Tejel, Vogtenhuber, Weinberger
Shooting Stars in Simple Drawings of K_m,n (🍭)	Aichholzer, García, Parada, Vogtenhuber, Weinberger
Mutual Witness Gabriel Drawings of Complete Bipartite Graphs	Lenhart, Liotta
FORBID: Fast Overlap Removal By stochastic gradIent Descent for Graph Drawing	Giovannangeli, Lalanne, Giot, Bourqui
Planar Confluent Orthogonal Drawings of 4-Modal Digraphs	Cornelsen, Diatzko
Strictly-Convex Drawings of 3-Connected Planar Graphs (🌶️)	Bekos, Gronemann, Montecchiani, Symvonis
st-Orientations with Few Transitive Edges	Binucci, Didimo, Patrignani
Planarizing Graphs and their Drawings by Vertex Splitting	Nöllenburg, Sorge, Terziadis, Villedieu, Wu, Wulms
An FPT Algorithm for Bipartite Vertex Splitting (🍭)	Ahmed, Kobourov, Kryven
Small Point-Sets Supporting Graph Stories	Di Battista, Didimo, Grilli, Grosso, Ortali, Patrignani, Tappini
On the Complexity of the Storyplan Problem	Binucci, Di Giacomo, Lenhart, Liotta, Montecchiani, Nöllenburg, Symvonis
Queue Layouts of Two-Dimensional Posets (🍭)	Pupyrev
The Rique-Number of Graphs (🌶️)	Bekos, Felsner, Kindermann, Kobourov, Kratovíl, Rutter
Visibility Representations of Toroidal and Klein-bottle Graphs	Biedl

Die mit einer Chilischote (🌶️) gekennzeichneten Themen sind dahingehend etwas anspruchsvoller, dass Techniken aus der Vorlesung Visualisierung von Graphen zum Einsatz kommen - diese besucht zu haben ist deshalb für die Bearbeitung dieser Themen sehr empfohlen.

Die mit Zuckerwerk (🍭) gekennzeichneten Artikel sind weniger umfangreich als die übrigen Themen. Dies sollte jedoch nicht fälschlicherweise mit weniger Bearbeitungsaufwand gleichgesetzt werden. Wer eines dieser Themen wählt, muss damit rechnen, etwas mehr eigene Literaturrecherche betreiben zu müssen oder einen der ersten Vortragstermine mit weniger Vorbereitungszeit zugewiesen zu bekommen. Es ist eben kein Zuckerschlecken.

Lernziele

Ziel ist es, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen Kursteilnehmern und -teilnehmerinnen in einem Vortrag zu vermitteln.

Sie bekommen im Seminar einen Überblick über Techniken der Graphvisualisierung und vertiefen ihre Kenntnisse über das Modellieren und Lösen von Problemen mithilfe von Graphen und Graphalgorithmen, sowie über parametrisierte Komplexität. Dieses Thema eignet sich übrigens auch gut für Abschlussarbeiten.

Module

Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik eingetragen.

Allgemeine Literatur zum Graphzeichnen

Graph Drawing: Algorithms for the Visualization of Graphs
Giuseppe Di Battista, Peter Eades, Roberto Tamassia und Ioannis G. Tollis. Prentice Hall, 1998.
The Handbook of Graph Drawing and Visualization
Roberto Tamassia (Hrsg.). CRC Press, 2014.
Drawing Graphs: Methods and Models
Michael Kaufmann und Dorothea Wagner (Hrsg.), Lecture Notes in Computer Science, Band 2025. Springer-Verlag, 2001.
Planar Graph Drawing
Takao Nishizeki und Md Saidur Rahman, Lecture Notes Series on Computing, Band 12. World Scientific Publishing, 2004.