Bölüm: Seminar: Visualisierung von Graphen | SS24: Seminar Algorithmik

Bölüm anahatları

Umfang:	5 ECTS, 2 SWS
Zeit & Ort:	dienstags, 16:00–17:30 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. Für einige Theman kann Vorwissen aus einer der Masterveranstaltungen Visualisierung von Graphen, Algorithmische Geometrie oder Exakte Algorithmen hilfreich sein, ist aber nicht erforderlich.
Zielgruppe:	Master Informatik (empfohlen), Bachelor Informatik
Dozenten:	Johannes Zink, Boris Klemz und Diana Sieper

Wenn Sie am Seminar teilnehmen möchten, kommen Sie zum ersten Termin am Dienstag, den 16.04.2024, um 16:00 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: Allgemeine Themen der Algorithmik

In diesem Semester deckt das Seminar einen weiten Bereich des Themenfelds Algorithmik ab. Die meisten Themen beziehen sich auf sehr aktuelle Forschungsergebnisse, einige sind ältere Klassiker. Betrachtet werden dabei hauptsächlich eher theoretische Erkenntnisse. Im Seminar kommen Methoden aus den Vorlesungen Algorithmen und Datenstrukturen, sowie Algorithmischer Graphentheorie zum Einsatz. Für einige Themen kann es hilfreich sein, eine der Vorlesungen Visualisierung von Graphen, Algorithmische Geometrie oder Exakte Algorithmen gehört zu haben, es ist 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 Praktika, sowie Abschlussarbeiten im Anschluss an das Seminar führen.

Thema	Quellen (bei mehr als eine Quelle ist die Hauptquelle hervorgehoben)
Global and local edge-length ratios of planar straight line graph drawings	https://arxiv.org/abs/2311.14634, https://www.sciencedirect.com/science/article/pii/S0304397518306078?vi%3Dihub, https://jocg.org/index.php/jocg/article/view/3096, https://www.worldscientific.com/doi/abs/10.1142/S0218195921500072
Recognition Complexity of Subgraphs of 2- and 3-Connected Planar Cubic Graphs	https://arxiv.org/abs/2401.05892,
Min-k-planar Drawings of Graphs	https://arxiv.org/abs/2308.13401
On RAC Drawings of Graphs with Two Bends per Edge	https://arxiv.org/abs/2308.02663
Edge-disjoint Plane Spanning Paths in a Point Set	https://www.sciencedirect.com/science/article/pii/S0020019017300637, https://arxiv.org/abs/2306.07237
Parameterized Complexity of Simultaneous Planarity	https://arxiv.org/abs/2308.11401
Removing Popular Faces in Curve Arrangements	https://arxiv.org/abs/2202.12175
Computing the Enclosing Depth	https://arxiv.org/abs/2402.12371
Robust Bichromatic Classification with Lines	https://arxiv.org/abs/2401.02897
Clustering with Few Disks to Minimize the Sum of Radii	https://arxiv.org/abs/2312.08803, https://epubs.siam.org/doi/10.1137/100798144
Approximations for Maximum-Leaf Spanning Tree	https://arxiv.org/abs/2303.03125
NP-hard Puzzle Games: Tetris, Nondango	https://arxiv.org/abs/2310.11447, https://arxiv.org/abs/cs/0210020, https://arxiv.org/abs/2009.14336
On the Complexity of Lombardi Graph Drawing	https://arxiv.org/abs/2306.02649
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions	https://link.springer.com/content/pdf/10.1007/s00453-009-9296-1.pdf
Solving 2-SAT in Linear Time	Wird im Seminar / per Email kommuniziert.

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

Oksana Firman

Tim Hegemann

Boris Klemz

Felix Klesen

Marie Sieper

Alexander Wolff

Johannes Zink

Bölüm anahatları