Ämnesdisposition
-
Umfang:
5 ECTS, 2 SWS
Zeit & Ort:
dienstags, 14:15–15:45 Uhr, online
Voraussetzung:
Algorithmische Graphentheorie (empfohlen)
Zielgruppe:
Master Informatik (empfohlen), Bachelor Informatik
Dozenten:
Der erste Termin findet am Di, 03.11.2020, um 14:15 Uhr als Zoom-Meeting statt. 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 Anzahl der TeilnehmerInnen jeweils alleine oder zu zweit bearbeitet.
Senden Sie uns bitte per Email vor dem ersten Treffen, bis Mo., 02.11.2020, 13:00 Uhr, Ihre ersten drei Präferenzen sowie Ihren Studiengang (BSc/MSc) und Ihre algorithmischen Vorkenntnisse (welche Vorlesungen haben Sie in der Algorithmik gehört?). Nennen Sie auch gerne den Namen einer weiteren Person mit der Sie ggf. gemeinsam ein Thema bearbeiten würden.
Wir werden anschließend anhand Ihrer Präferenzen eine Themenverteilung festlegen. (Falls Sie uns Ihre Präferenzen nicht rechtzeitig geschickt haben, besteht auch noch während des ersten Treffens die Möglichkeit sich für eines der übrig gebliebenen Themen zu melden.)
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.)
-
Thema
Wir beschäftigen uns mit Algorithmen zum Zeichnen von Graphen. Dabei kommen Methoden aus der Vorlesung Algorithmische Graphentheorie wie beispielsweise Teile und Herrsche, Flussnetzwerke, ganzzahlige Programmierung und das Planar-Separator-Theorem zum Einsatz. Mit Hinblick auf das Thema des Graph Drawing Wettbewerbs 2021 wurden einige Artikel ausgewählt, die sich mit dem Anfertigen von Zeichnungen beschäftigen, in denen alle Kanten möglichst gleiche Länge haben. Abweichend vom eigentlichen Thema des Seminars wurde auch ein Artikel zur Bewegungsplanung von Robotern ausgewählt, anlässlich der kürzlich angekündigten Computational Geometry Challenge 2021. Das kann zu Themen für Praktika oder für Abschlussarbeiten führen.
Titel AutorInnen On the edge-length ratio of outerplanar graphs
Lazard, Lenhart, Liotta On the planar edge-length ratio of planar graphs Borazzo, Frati On the edge-length ratio of 2-trees Blažej, Fiala, Liotta Odd wheels are not odd-distance graphs Damasi The Local Queue Number of Graphs with Bounded Treewidth
Merker, Ueckerdt Parameterized Algorithms for Queue Layouts Bhore, Ganian, Montecchiani, Nöllenburg
Schematic Representation of Large Biconnected Graphs Di Battista, Frati, Patrignani, Tais
Planar L-Drawings of Bimodal Graphs Angelini, Chaplick, Cornelsen, Da Lozzo
Towards a characterization of stretchable aligned graphs Radermacher, Rutter, Stumpf
Drawing Shortest Paths in Geodetic Graphs * Cornelsen, Pfister, Förster, Gronemann, Hoffmann, Kobourov, Schneck
Augmenting Geometric Graphs with Matchings
Rollin, Pilz, Schlipf, Schulz
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch Demaine, Fekete, Keldenich, Meijer, Scheffer
*) Dieses Thema wird nur bei großer TeilnehmerInnenzahl vergeben. In diesem Fall wird es sich um den ersten Vortrag des Seminars handeln. Sie dürfen vier statt drei Präferenzen angeben, falls Sie dieses Thema mit aufführen.Lernziele
Die TeilnehmerInnen lernen, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen KursteilnehmerInnen 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. 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.
- Graph Drawing: Algorithms for the Visualization of Graphs
-
-
- Im ersten Treffen werden wir den Ablauf des Seminars besprechen und die Themenverteilung festlegen.
- Im zweiten Treffen gibt jeder Teilnehmer einen kurzen Überblick über sein Thema (max. 5 Minuten, 3 Folien). Außerdem werden wir Genaueres zur Gestaltung der Vorträge und der Ausarbeitung sagen.
- In den folgenden Treffen finden die eigentlichen Vorträge der TeilnehmerInnen statt. Neben dem Vortrag bleibt auch Zeit zur Diskussion der Themen und daraus resultierender offener Fragen für die weitere Forschung.
- Desweiteren ist zu jedem Thema eine Ausarbeitung anzufertigen.
-
Grundlage jedes Vortragsthemas sind ein oder mehrere wissenschaftliche Artikel. Die Themen basieren meist auf aktuellen Forschungsergebnissen, die beispielsweise auf dem 28th International Symposium on Graph Drawing & Network Visualization (GD 2020) vorgestellt wurden.
Für jedes Thema geben wir einen Artikel bzw. ein Buchkapitel vor. Sie sollen aber auch noch selbst Literaturrecherche betreiben. Ein Ausgangspunkt dafür können beispielsweise die Referenzen in ihrem Artikel sein. Da wir das Seminar auf die aktuelle Forschung hin ausrichten wollen, sind insbesondere offene Fragen ein wichtiger Bestandteil der Themen.
-
- Ihr Vortrag sollte etwa 45 Minuten (bei Einzelvorträgen) bzw. 60 Minuten (zu zweit) dauern.
- Wir empfehlen für die Erstellung der Folien das kostenlose Programm ipe (verfügbar für Linux, Windows, Mac). Als Einstieg können Sie gerne einen Blick auf die Folien vom Einführungsvortrag werfen. Die PDF-Datei können Sie mit ipe öffnen und weiterbearbeiten.
- Im Vortrag sollten auch relevante offene Forschungsfragen nicht zu kurz kommen.
- Die Folien Ihres Vortrages werden wir anschließend hier für alle TeilnehmerInnen zur Verfügung stellen.
-
Die Ausarbeitung zu ihrem Thema sollte etwa 10 Seiten (zuzüglich Titelseite) umfassen. Sie soll nicht nur den von uns vorgegebenen Artikel zusammenfassen, sondern auch darüber hinaus gehen. Zum Einen eignet sich dafür das Material, dass sie durch eigene Literaturrecherche gefunden haben. Zum anderen kann man hier auch auf interessante offene Fragen eingehen.
Die Themen des Seminars sollen nicht für sich alleine stehen, sondern wurden bewusst aus einem bestimmten Gebiet gewählt. Nutzen Sie das in ihrer Ausarbeitung und zeigen Sie Verbindungen zu anderen Vortragsthemen des Seminars auf! Vielleicht können Sie dadurch auch neue Fragestellungen entwickeln, die für die weitere Forschung interessant sind. Damit Sie die Möglichkeit haben Ergebnisse aus den anderen Vorträgen in Ihre Ausarbeitung aufzunehmen, muss diese erst eine Woche nach dem letzten Vortrag abgegeben werden.
Die Ausarbeitungen sollen mit LaTeX erstellt werden. Wenn Sie noch keine Erfahrung mit LaTeX haben, könnte dieser kostenlose Kurs im Rechenzentrum hilfreich sein.
-
Voraussetzungen für das Bestehen des Seminars:
- Halten einer Präsentation zum gewählten Thema
- Anfertigen einer Ausarbeitung
- Regelmäßige Teilnahme am Seminar und aktive Mitarbeit (einmaliges Fehlen bei einem Vortrag ist erlaubt)