Section: Seminar: Visualisierung von Graphen – mit Fokus auf parametrisierte Algorithmen | WS21: 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:	Algorithmische Graphentheorie (empfohlen)
Zielgruppe:	Master Informatik (empfohlen), Bachelor Informatik
Dozenten:	Alexander Wolff und Johannes Zink

Wenn Sie am Seminar teilnehmen möchten, kommen Sie zum ersten Termin am Dienstag, den 19.10.2021, um 14:15 Uhr – dieser wie auch das gesamt 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 bereits jetzt 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 bearbeiten möchten.

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 Sie auf den blauen Knopf links oben mit den weißen Zahnrädern und dort auf "Mich in diesen Kurs einschreiben". (Entsprechend können Sie sich natürlich auch wieder austragen.)

Hauptthema in diesem Semester: Parametrisierte Algorithmen beim Graphenzeichnen

Der Fokus des Seminars in diesem Semester liegt auf der Schnittmenge von parametrisierten Algorithmen (FPT) und dem algorithmischen Zeichnen von Graphen. Ein noch relativ wenig untersuchtes Feld, das noch viel offen hält. Daneben beschäftigen wir uns aber auch mit einigen Themen zum Zeichnen von Graphen ohne Bezug auf Parametrisierung. Im Seminar kommen Methoden aus der Vorlesung 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. Außerdem kann es das Thema eines Praktikums oder einer Abschlussarbeit im Anschluss an das Seminar werden.


Titel	Autoren
Parameterized Algorithms for Book Embedding Problems	Bhore, Ganian, Montecchiani, Nöllenburg
On the Upward Book Thickness Problem: Combinatorial and Complexity Results	Bhore, Da Lozzo, Montecchiani, Nöllenburg
Exact Crossing Number Parameterized by Vertex Cover	Hliněný, Sankaran
On the Parameterized Complexity of Layered Graph Drawing [Konferenzversion\|Journalversion]	Dujmović, Fellows, Hallett, Kitching, Liotta, McCartin, Nishimura, Ragde, Rosamond, Suderman, Whitesides, Wood
Fixed parameter algorithms for ONE-SIDED CROSSING MINIMIZATION revisited	Dujmovíc, Fernau, Kaufmann
Connecting the Dots (with Minimum Crossings)	Agrawal, Guśpiel, Madathil, Saurabh, Zehavi
Planar Straight-line Realizations of 2-Trees with Prescribed Edge Lengths	Alegría, Borrazzo, Da Lozzo, Di Battista, Frati, Patrignani
Arrangements of orthogonal circles with many intersections	Carmesin, Schulz
Recognizing and Embedding Simple Optimal 2-Planar Graphs	Förster, Kaufmann, Raftopoulou
A short proof of the non-biplanarity of K₉	Biniaz
RAC-drawability is ∃ℝ-complete	Schaefer
Embedding Ray Intersection Graphs and Global Curve Simplification	van de Kerkhof, Kostitsyna, Löffler

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.

Literatur zu Festparameter-Berechenbarkeit (FPT)

Parameterized Complexity
Rodney Downey, Michael Fellows. Monographs in Computer Science, Springer-Verlag , 1999.
Parameterized Complexity Theory
Jörg Flum, Martin Grohe. Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, 2006
Invitation to Fixed-Parameter Algorithms
Rolf Niedermeier. Oxford University Press, 2006
Kernelization: Theory of Parameterized Preprocessing
Fomin, Lokshtanov, Saurabh, Zehavi. Cambridge University Press, 2019
Parameterized Algorithms (pdf-Download über Shibboleth und den Uni-Login)
Fomin, Lokshtanov, Saurabh, Zehavi. Kapitel in Beyond the Worst-Case Analysis of Algorithms, Cambridge University Press, 2020