Sinn dieses Seminars ist es, sich mit einem Themengebiet aus dem Bereich der Layoutalgorithmen intensiv und selbständig wissenschaftlich auseinanderzusetzen. Das Thema ist in einem mündlichen Vortrag und einer schriftlichen Ausarbeitung zusammenzufassen. Ein weiterer Sinn dieses Seminars ist es, das Arbeiten in strukturierten zeitlichen Abläufen zu üben, wie es z.B. für Workshops/Tagungen üblich ist. Beide Aspekte sind erfahrungsgemäß eine gute Vorbereitung auf die Anfertigung einer Abschlussarbeit. Es sind auch diverse Abschlussarbeitsthemen (Bachelor oder Master) auf diesem Themengebiet zu vergeben; bei Interesse sprechen Sie uns bitte an.

Dieses Seminar wird in zwei Varianten angeboten, als Bachelor-Modul und als Master-Modul. Im Vergleich zum Bachelorseminar erwartet das Masterseminar eine größere Einbeziehung von verwandten Arbeiten, und dementsprechend eine umfangreichere Ausarbeitung und Präsentation (siehe unten).

Beispiele

Section
Image Removed Column width 49% Column width 49% Image Removed Image Removed Image Removed Image Added

Wichtige Eckdaten

Themen

Master-Studenten meiden bitte den Themenbereich Traditional Methods.

Traditional Methods [uru]

[vergeben] Reingold, E. M., & Tilford, J. S. (1981). Tidier Drawings of Trees. IEEE Transactions on Software Engineering, 7(2), 223–228.

[vergeben] Sugiyama, K., Tagawa, S., & Toda, M. (1981). Methods for Visual Understanding of Hierarchical System Structures. IEEE Transactions on Systems, Man and Cybernetics, 11(2), 109–125.

[vergeben] Tamassia, R., Battista, G. Di, & Batini, C. (1988). Automatic Graph Drawing and Readability of Diagrams. IEEE Transactions on Systems, Man and Cybernetics, 18(1), 61–79.

[vergeben] Fruchterman, T., & Reingold, E. (1991). Graph drawing by force directed placement. Software: Practice and Experience, 21(11), 1129–1164.

Planarization [uru]

[vergeben] Jayakumar, R., Thulasiraman, K., & Swamy, M. N. S. (1989). O(n^2) Algorithms for Graph Planarization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8(3), 257–267.

[vergeben] Klau, G. W., & Mutzel, P. (1999). Combining graph labeling and compaction. In Proceedings of Graph Drawing, 7th International Symposium, GD'99, Stirín Castle, Czech Republic, September 1999 (pp. 27-37).

[vergeben] Eiglsperger, M., & Kaufmann, M. (2002). Fast Compaction for orthogonal drawings with vertices of prescribed size. In Proceedings of Graph Drawing, 9th International Symposium, GD'01, Vienna, Austria, September 23-26, 2001 (pp. 124-138).

Gutwenger, C., Mutzel, P., & Weiskircher, R. (2005). Inserting an edge into a planar graph. Algorithmica, 41(4), 289–308.

Label Placement [nbw/cds]

[vergeben, cds] Edmondson, S., Christensen, J., Marks, J., & Shieber, S. (1996). A general cartographic labeling algorithm. Cartographica, 33(4), 13–23.

[vergeben, nbw] Wolff, A., Knipping, L., van Kreveld, M. J., Strijk, T., & Agarwal, P. K. (2002). A simple and efficient algorithm for high-quality line labeling.

[vergeben, cds] Dogrusoz, U., Kakoulis, K. G., Madden, B., & Tollis, I. G. (2007). On labeling in graph visualization. Information Sciences, 177(12), 2459–2472.

Edge Label User Studies [nbw]

[vergeben] Holten, D., & Van Wijk, J. J. (2009). A user study on visualizing directed edges in graphs. In Proceedings of the 27th International Conference on Human Factors in Computing Systems (CHI), Boston, MA, USA, April 4-9, 2009 (pp. 2299–2308).

[vergeben] Holten, D., Isenberg, P., Van Wijk, J. J., & Fekete, J. D. (2011). An extended evaluation of the readability of tapered, animated, and textured directed-edge representations in node-link graphs. In Proceedings of the 2011 IEEE Pacific Visualization Symposium, PacificVis 2011, Hong Kong, China, March 1-4, 2011 (pp. 195–202).

[vergeben] Xu, K., Rooney, C., Passmore, P., Ham, D. H., & Nguyen, P. H. (2012). A user study on curved edges in graph visualization. IEEE Transactions on Visualization and Computer Graphic, 18(12), 2449–2456.

Human Computer Interaction [nbw]

[vergeben] Taylor, M., & Rodgers, P. (2005). Applying graphical design techniques to graph visualisation. In Proceedings of the 9th International Conference on Information Visualisation, IV 2005, 6-8 July 2005, London, UK (pp 651–656).

[vergeben] Lutz, R., Rausch, D., Beck, F., & Diehl, S. (2014). Get your directories right: From hierarchy visualization to hierarchy manipulation. In Proceedings of the 2014 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), Melbourne, VIC, Australia, July 28 - August 1, 2014 (pp. 25–32).

[vergeben] Sato, Y., Masuda, S., Someya, Y., Tsujii, T., & Watanabe, S. (2015). An fMRI analysis of the efficacy of Euler diagrams in logical reasoning. In Proceedings of 2015 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), Atlanta, GA, USA, October 18-22, 2015 (pp. 143–151).

Termine

Ablauf

Automatic Graph Drawing and Readability of Diagrams

Tidier Drawings of Trees

Graph drawing by force directed placement

O(n^2) Algorithms for Graph Planarization

Combining graph labeling and compaction

A general cartographic labeling algorithm

A simple and efficient algorithm for high-quality line labeling

On labeling in graph visualization

A user study on curved edges in graph visualization

A user study on visualizing directed edges in graphs

An extended evaluation of the readability of tapered, animated, and textured directed-edge representations in node-link graphs

Applying graphical design techniques to graph visualisation

Get your directories right: From hierarchy visualization to hierarchy manipulation

An fMRI analysis of the efficacy of Euler diagrams in logical reasoning

Organisatorische Details und Benotung

Auch wenn das Einchecken von generierten Binärdateien generell eher vermieden werden sollte, sind für dieses Seminar auch die folgenden pdfs einzuchecken, um unnötige Compilierungsschwierigkeiten bei Dozenten und Reviewern zu vermeiden. Grafiken sollten in einem Unterordner (z.B. "images") abgelegt werden. Grafiken sollten weiterhin möglichst skalierbare  Verktorgrafiken sein, die als PDF eingebunden werden können. Nicht einzuchecken sind temporäre Dateien (.aux etc.).

Die Namen für die Dateien, die im Git abzulegen sind, sollen wie folgt (gleichartig) aufgebaut sein. Bitte halten Sie sich von Anfang an an diese Namenskonventionen. Das vermeidet unnötige Sucherei, bewahrt uns vor späteren Schwierigkeiten mit automatischen Skripten und macht umständliches Umbenennen überflüssig.

• Ausarbeitung: <login>/sem16ws-<login>.[tex/pdf]
• Vortragsfolien: <login>/sem16ws-<login>-talk.[tex/pdf]
• Handoutfolien - ohne Animationen, für Ausdrucke und die Proceedings: <login>/sem16ss-<login>-handout.[tex/pdf]
• Review (generelle Anmerkungen): <login review-Empfänger>/sem16ss-<login review-Empfänger>-reviewnotes-<login Reviewer>.[pdf]
• Review (annotiertes PDF): <login review-Empfänger>/sem16ws-<login review-Empfänger>-review-<login Reviewer>.[pdf] (Beispiel also: Ulf (uru) reviewt die Ausarbeitung von Nis (nbw) und checkt das Review-PDF mit dem Namen sem16ss-nbw-review-uru.pdf im Ordner uru des Seminarrepositorys ein.

Anmerkung: Die Handoutfolien unterscheiden sich von den Vortragsfolien dadurch, dass die Handoutfolien keine Animationen für die Präsentation am Beamer enthalten. Beim Arbeiten mit der latex-beamer Klasse können Handoutfolien durch das Hinzufügen eines optionalen Argumentes bei der Deklaration der Dokumentenklasse generiert werden ("\documentclass[trans]{beamer}").

Technisches

• Reichlich Dokumentation zum Git Source Code Management System findet man unter http://www.git-scm.com/.
• Für den Zugriff auf das Repository müssen wir Sie in unserem  Bitbucket  dafür freischalten. Das sollten wir anhand der Teilnehmerliste prima tun können. Falls Sie keinen Zugriff auf das Repository bekommen, schreiben Sie uns eine E-Mail.
• Git-Repository auschecken: git clone  ssh://git@git.rtsys.informatik.uni-kiel.de:7999/sem/16ws-layout.git
  
  • Um die Erstellung der Proceedings zu erleichtern, richten Sie sich bitte nach den oben beschriebenen Namenskonventionen.
• ACM Style in deutscher oder englischer Version. Im Git Repository befinden sich im Unterverzeichnis init/ eine Reihe von Dateien, welche Sie als Vorlage nehmen können (siehe README.txt).
• Wir benutzen pdflatex (erstellt PDF Dateien) und nicht direkt latex (erstellt DVI Dateien)
  • sind im Prinzip gleich zu benutzen
  • Hauptunterschied ist die Einbindung von Grafiken. In pdflatex siehe z.B. http://latex.mschroeder.net/#grafiken (Es sollte immer eine komplette figure Umgebung mit caption, label und Referenz im Text benutzt werden!)
  • Von der Kommandozeile aus kann ein pdf mit "rubber -d sem15ss-<login>" erstellt werden (rubber ruft automatisch pdflatex und bibtex auf).

• Bibliographie: Siehe ACM Beispiel (hier werden die Bibliographielemente in eine eigene *.bib Datei ausgelagert). Manuell wird dann einmal pdflatex dokument.tex aufgerufen. Dies erzeugt eine dokument.aux Datei. Darauf wird bibtex dokument.aux aufgerufen und dann nochmal zweimal pdflatex dokument.tex. Erst dann sind die Bibliographieelemente richtig im pdf-file.

Technische Details

Ressourcen