Bölüm: Seminar: Praktische und theoretische Aspekte des Graphenzeichnens | SS20: Seminar Praktische und theoretische Aspekte des Graphenzeichnens

Bölüm anahatları

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:	Alexander Wolff und Johannes Zink
Kooperationspartner:	Infosim (Würzburg) und denkbares (Würzburg)

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

Folien zum Ablauf und Erklärung der Themen etkinliğini seçin

Folien zum Ablauf und Erklärung der Themen Dosya

Ü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
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 Programm	Sven 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 Graphenzeichnen	Ulrik 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/8462766	noch 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/4069239	noch 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.