Topic outline
Seminar: Praktische und theoretische Aspekte des Graphenzeichnens
Umfang:
5 ECTS
Zeit & Ort:
Themenvergabe online, wenn möglich Vorträge bei Blocktermin(en) Freitag Mittag/Nachmittag im Juli
Voraussetzung:
Algorithmische Graphentheorie (mit Nachdruck empfohlen)
Zielgruppe:
Master Informatik (vorzugsweise), Bachelor Informatik
Dozenten:
Kooperationspartner:
Aufgrund der aktuellen Situation in der Coronakrise erfolgt (mindestens) die Themenvergabe online. Wir listen hier alle Themen mit Folien zur Erklärung dieser Themen auf und Sie senden uns bitte bis Fr., 24.04.2020, 10:00 Uhr Ihre ersten drei Präferenzen sowie ihren Studiengang (BSc/MSc) und algorithmischen Vorkenntnisse (welche Vorlesungen haben Sie in der Algorithmik gehört?).
Themen, die danach noch offen sind, können sie anschließend per Email noch nachbelegen.
Für Fragen wenden Sie sich gerne jederzeit an uns per Email! Gerade wenn die persönlichen Kontaktmöglichkeiten eingeschränkt sind, ist es wichtig diese Kommunikationsmöglichkeiten zu nutzen.
Bitte schreiben Sie sich schon vorher in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen wollen.
(Klicken Sie dazu im Kursraum ganz oben links auf das Feld mit den weißen Zahnrädern auf blauem Grund und wählen Sie dann "Mich in diesem Kurs einschreiben" aus.)Überblick
Wir beschäftigen uns mit verschiedenen Aspekten von Algorithmen zum Zeichnen von Graphen. Dabei sind sowohl praktische Anwendungsmöglichkeiten als auch theoretische Hintergründe interessant. In diesem Seminar stehen praktische Umsetzungsmöglichkeiten (z. B. aus dem Algorithm-Engineering) und deren Analyse mehr im Fokus als bei unserem Seminar Visualisierung von Graphen, das wir im Wintersemester anbieten.
Das Seminar wird in Kooperation mit den zwei Würzburger IT-Unternehmen Infosim und denkbares durchgeführt, welche auch teilweise die Betreuung bestimmter Themen übernehmen und zu denen so auch ein Kontakt hergestellt und ein Einblick auch für etwaige spätere Tätigkeiten gewonnen werden kann.
Themen
Alle Teilnehmer und Teilnehmerinnen sollen durch die eigene Arbeit und das Hören der anderen Vorträge einen Überblick über praktische und theoretische Aspekte des Graphenzeichnens bekommen. 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 auch auf die aktuelle Forschung hin ausrichten wollen, sind insbesondere offene Fragen ein wichtiger Bestandteil der Themen. Wenn es das eigene Thema anbietet, so können und sollen auch selbst die untersuchten Konzepte einmal grob implementiert werden bzw. vorhandene Programme einmal ausprobiert werden. Dies kann dann als kleine Demonstration Teil des Abschlussvortrags gegen Ende des Semesters sein und möglicherweise als Grundlage für weitere Arbeiten dienen.
Thema
Autoren
Artikel
Konf./Journal Link Bearbeitet Betreut
Vortrag Graphen mit guter Winkelauflösung
Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Parada, Daniel Perz, André van Renssen, Birgit Vogtenhuber
Graphs with large total angular resolution
GD 2019
https://arxiv.org/abs/1908.06504
TG
Symmetrien in Graphzeichnungen Felice De Luca, Stephen Kobourov, Helen Purchase Perception of Symmetries in Drawings of Graphs GD 2018 https://arxiv.org/abs/1808.01031 noch offen Ästhetikbewertung von Zeichnungen mittels neuronalen Netzen Moritz Klammler, Tamara Mchedlidze, Alexey Pak Aesthetic Discrimination of Graph Layouts J. Graph Algorithms Appl. 2019 http://jgaa.info/getPaper?id=501 noch offen Graphenzeichnen mit Zeitdimension (I) Manuel Borrazzo, Giordano Da Lozzo, Fabrizio Frati, Maurizio Patrignani Graph Stories in Small Area GD 2019 https://arxiv.org/abs/1908.09318 noch offen Graphenzeichnen mit Zeitdimension (II) Paolo Simonetto, Daniel Archambault, Stephen Kobourov Drawing Dynamic Graphs Without Timeslices GD 2017 https://arxiv.org/abs/1709.00372 noch offen Lagenbasiertes
Graphenzeichnen mit quadratischem ProgrammSven Mallach A Natural Quadratic Approach to the Generalized Graph Layering Problem GD 2019 https://arxiv.org/abs/1908.04104 noch offen Grundlegende
Koordinatenzuweisung beim hierarchischen GraphenzeichnenUlrik Brandes, Boris Köpf Fast and Simple Horizontal Coordinate Assignment GD 2001 https://link.springer.com/chapter/10.1007/3-540-45848-4_3 noch offen Koordinatenzuweisung beim hierarchischen Graphenzeichnen mittels Flussnetzwerk Michael Jünger, Petra Mutzel, Christiane Spisla A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width J. Graph Algorithms Appl. 2019 http://jgaa.info/getPaper?id=500 noch offen Lagenzuweisung beim hierarchischen Graphenzeichnen Ulf Rüegg, Thorsten Ehlers, Miro Spönemann, Reinhard von Hanxleden Generalized Layerings for Arbitrary and Fixed Drawing Areas J. Graph Algorithms Appl. 2017 http://jgaa.info/getPaper?id=441 noch offen Stressminimierung beim kräftebasierten Graphenzeichnen Mark Ortmann, Mirza Klimenta, Ulrik Brandes A Sparse Stress Model J. Graph Algorithms Appl. 2017 http://jgaa.info/getPaper?id=440 noch offen Kräftebasierter Multilevel-Zeichenalgorithmus bei verteilter Berechnung Alessio Arleo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani A Distributed Multilevel Force-directed Algorithm IEEE Trans. Parallel Distrib. Syst. 2019 https://arxiv.org/pdf/1608.08522.pdf
und im vpn auch:
https://ieeexplore.ieee.org/document/8462766noch offen Topologieabhängiger Multilevel-Zeichenalgorithmus
Daniel Archambault, Tamara Munzner, David Auber TopoLayout: Multilevel Graph Layout by Topological Features IEEE TVCG 2007 im vpn:
https://ieeexplore.ieee.org/document/4069239noch offen Biologische Diagramme automatisiert im Stil eines Stadtplans zeichnen Hsiang-Yun Wu, Martin Nöllenburg, Filipa L. Sousa, Ivan Viola Metabopolis: scalable network layout for biological pathway diagrams in urban map style BMC BI 2019 https://doi.org/10.1186/s12859-019-2779-4 DH
Die Artikel können Sie über die Links herunterladen, die meisten auch außerhalb des Uninetzes. Anderenfalls wenden Sie sich an uns.
Lernziele
Die Teilnehmer und Teilnehmerinnen lernen, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen Kursteilnehmern in einem Vortrag zu vermitteln.
Sie bekommen im Seminar einen Überblick über Techniken und Anwendungsfelder 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.
Außerdem sollen sie einen Eindruck von Forschung in der Informatik bekommen: vom Erkennen und Formulieren geeigneter Problemstellungen über das Entwickeln von Lösungsstrategien für diese Probleme bis zum Festhalten der Ergebnisse in einer wissenschaftlichen Arbeit.
Module
Unser Seminar richtet sich in erster Linie an Studenten und Studentinnen im Master Informatik, welche wir bei der Themenwahl evtl. bevorzugen werden.
Darüber hinaus können aber auch interessierte Studenten und Studentinnen im Bachelor Informatik (oder ähnliches) daran teilnehmen.
Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik eingetragen. Bei großem Engagement über den Vortrag und die Ausarbeitung hinaus (siehe Ablauf), wäre auch eine Anrechnung als Praktikum denkbar.
Ablauf
- Auf dieser WueCampus-Seite werden wir einen Überblick über die Themen geben. Sehen Sie sich auch die beiliegenden Folien an, die die Themen erklären sollen. Wenn Sie dennoch Fragen zu einem Thema oder Organisatorischem haben, schreiben Sie uns eine Email!
- Senden Sie uns bitte bis Fr., 24.04.2020 Ihre ersten drei Präferenzen sowie ihren Studiengang (BSc/MSc) und algorithmischen Vorkenntnisse (welche Vorlesungen haben Sie in der Algorithmik gehört?) per Email. Wir versuchen Ihre Themenwünsche so gut wie möglich zu erfüllen. Wir werden Ihnen danach per Email mitteilen, welches Thema Sie erhalten haben und wer Sie betreuen wird. Das kann ein Mitarbeiter der Universität oder der Firmen Infosim oder denkbares sein. Wenn Sie hier Präferenzen haben, teilen Sie uns das bitte im Vorfeld mit, da wir die Betreuung themenabhängig zuweisen.
- Halten Sie am 08.05.2020 online einen Kurzvortrag über etwa 5 Minuten (ca. 3 Folien). Der Kurzvortrag ist unbenotet und für Sie als Übung gedacht – diese Semester auch, um einen Vortrag online zu halten. Für die meisten von uns eine neue Erfahrung. Außerdem soll der Kurzvortrag helfen, sich mit dem Thema auseinanderzusetzen und mögliche grundlegende Schwierigkeiten gleich zu Beginn aus dem Weg zu räumen.
- Sie setzen sich mit Ihrem Betreuer in Kontakt, um Ihr Thema zu besprechen und die Ausarbeitung vorzubereiten. Wenn zu dieser Zeit kein persönliches Treffen aufgrund der Einschränkungen der Coronakrise möglich ist, nutzen Sie gerne Streamingdienste für eine Online-Besprechung.
- Eine erste Version der schriftlichen Ausarbeitung soll bis 12.06.2020 dem Betreuer vorgelegt werden. Dieser gibt dann
Feedback, das in die finale Version eingebracht werden soll. Die finale Version ist bis zum 22.06.2020 abzugeben.
- Die folgenden Treffen im Juli gegen Ende des Semesters sind als Blockveranstaltung für die eigentlichen Vorträge der Teilnehmer gedacht. Neben dem Vortrag bleibt auch Zeit zur Diskussion der Themen und daraus resultierender offener Fragen für mögliche
weitere Forschung.
- Darüber hinaus besteht die Möglichkeit weiter an den untersuchten und vorgestellten Themen zu arbeiten und zu forschen.
Das kann im Rahmen einer Tätigkeit am Lehrstuhl für Informatik I sein, ggf. zusammen mit oder bei Infosim oder denkbares.
Termine
Termin Thema Vortragende
24.04.2020 Deadline für Themenwünsche (per Email einreichen)
08.05.2020
Kurzvorträge (online)
12.06.2020
Vorlage der vorläufigen Ausarbeitung beim Betreuer
22.06.2020
Abgabe der schriftlichen Ausarbeitung
03.07.2020
Vorlage der vorläufigen Folien beim Betreuer
10.07.2020 Blockvorträge
17.07.2020 Blockvorträge (wenn nötig)
Ausarbeitungen
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, das 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.
Die Ausarbeitungen sollen mit LaTeX erstellt werden. Wenn Sie noch keine Erfahrung mit LaTeX haben, könnte ein kostenloser LaTeX-Kurs im Rechenzentrum hilfreich sein.
Vorträge
- Ihr Vortrag sollte voraussichtlich 25–30 Minuten dauern und auch nicht länger sein (45–50 Minuten bei zwei Personen mit einem Thema). Wichtig: Die Dauer wird von der Anzahl der Seminar-TeilnehmerInnen abhängen.
- Wir empfehlen für die Erstellung der Folien das kostenlose Programm ipe (verfügbar für Linux, Windows, Mac).
Im Vergleich zu Powerpoint erleichtert es die Mischung von Text und Bildern. Man kann mit ipe geometrisch konstruieren und LaTeX-Befehle verwenden. - Ihr Vortrag kann auch offene Probleme ansprechen und vorhandene Programme/Demonstratoren können gezeigt werden.
- Die Folien ihres Vortrages stellen wir hier für alle Teilnehmer des Seminars zur Verfügung.
- Ihr Vortrag sollte voraussichtlich 25–30 Minuten dauern und auch nicht länger sein (45–50 Minuten bei zwei Personen mit einem Thema). Wichtig: Die Dauer wird von der Anzahl der Seminar-TeilnehmerInnen abhängen.