Real-Time and Embedded Systems

Seminar Layoutalgorithmen

AG Echtzeitsysteme und Eingebettete Systeme

Wintersemester 2014/15

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.

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

Voraussetzungen:

Für Diplomstudierende ist das Vordiplom Voraussetzung für die Teilnahme am Seminar.

Dozenten:

Reinhard v. Hanxleden (rvh@informatik.uni-kiel.de)
Christoph Daniel Schulze (cds@informatik.uni-kiel.de) 
Ulf Rüegg (uru@informatik.uni-kiel.de)

Themen

Zur Verfügung stehen folgende 15 Paper aus drei Themenbereichen. Ist ein Paper schon an jemanden vergeben vermerken wir das hier. Viele der Links werden nur aus dem Netz der Uni Kiel heraus funktionieren. Bei Problemen einfach Bescheid sagen.

Layout Aesthetics

  1. H. Purchase, C. Pilcher, B. Plimmer (2010). Graph Drawing Aesthetics - Created by Users not Algorithms. IEEE Transactions on Visualization and Computer Graphics (2010) (Link zum Download) (vergeben an Enno Schwanke)
  2. K. Marriott, H. Purchase, M. Wybrow, C. Goncu. Memorability of Visual Features in Network Diagrams. IEEE Transactions on Visualization and Computer Graphics (2012) (Link zum PDF) (vergeben an Sandra Skrlac)
  3. Q. Nguyen, P. Eades, S.-H. Hong. On the faithfulness of graph visualizations. 2013 IEEE Pacific Visualization Symposium (2013) (Link zum Download) (vergeben an David Gruner)
  4. C. Bennett, J. Ryall, L. Spalteholz, A. Gooch. The Aesthetics of Graph Visualization. Computational Aesthetics (2007) (Link zum PDF) (vergeben an Andreas Stange)
  5. P. Rodgers, L. Zhang, H. Purchase. Wellformedness properties in Euler diagrams: which should be used? IEEE Transactions on Visualization and Computer Graphics (2012) (Link zum PDF) (vergeben an Daniel Jahn)

Euler Diagrams and Higraphs

  1. J. C. Athenstädt, T. Hartmann, M. Nöllenburg. Simultaneous Embeddability of Two Partitions. Graph Drawing (2014) (Link zum Download)
  2. S. Chow, F. Ruskey. Drawing area-proportional Venn and Euler diagrams. Graph Drawing (2004) (Link zum PDF) (vergeben an Lasse Folger)
  3. J. Flower, A. Fish, J. Howse. Euler diagram generation. Journal of Visual Languages & Computing (2008) (Link zum Download) (vergeben an Heiko Brodersen)
  4. O. Grossman, D. Harel. On the algorithmics of Higraphs. Tech. Rep. CS97-15 (1997) (Link zum PS) (vergeben an Martin Bittermann)
  5. P. Mutton, P. Rodgers, J. Flower. Drawing graphs in Euler diagrams. Diagrammatic Representation and Inference (2004) (Link zum PDF) (vergeben an Carsten Sprung)
  6. N. Riche, T. Dwyer. Untangling Euler diagrams. IEEE Transactions on Visualization and Computer Graphics (2010) (Link zum Download) (vergeben an Mareike Struck)

Layout Methods

  1. R. Andreev, P. Healy, N. Nikolov. Applying Ant Colony Optimization Metaheuristic to the DAG Layering Problem. IEEE International Parallel and Distributed Processing Symposium (2007) (Link zum PDF) (vergeben an Tibor Weiß)
  2. T. Dwyer, N. Henry Riche, K. Marriott, C. Mears. Edge compression techniques for visualization of dense directed graphs. IEEE Transactions on Visualization and Computer Graphics (2013) (Link zum Download) (vergeben an Alan Schelten)
  3. S. Gladisch, H. Schumann. Semi-Automatic Editing of Graphs with Customized Layouts. Computer Graphics Forum (2014) (Link zum PDF) (vergeben an Lars Peiler)
  4. N. Nikolov, A. Tarassov, J. Branke. In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes. Journal of Experimental Algorithmics (2005) (Link zum Download) (vergeben an Daniel Grevismühl)
  5. X. Wang, I. Miyamoto. Generating customized layouts. Graph Drawing (1996) (Link zum Download) (vergeben an Lewe Andersen)

Termine (vorläufig):

27.10.
Frist für Themenauswahl (per Mail an Christoph Daniel und Ulf)
27.10. 13:30 Vorbesprechung/Kick-Off, LaTeX / Git Kurzeinführung (Raum 1011 im Uni-Hochhaus)
17.11. 08:00 Abgabe Ausarbeitungsgerüst (Abstract, Einleitung, Gliederung, Stichworte, Bibliographie)

20.11.
21.11.


Individualtermine
15.12. 08:00 Abgabe Erstversion der vollständigen Ausarbeitung
18.12.
19.12.

Individualtermine
06.01. 08:00

Abgabe der reviewbaren Version der Ausarbeitung 

06.01.
Zuordnung Ausarbeitungen/Reviewer (per E-mail)
12.01. 08:00 Abgabe der Reviews

19.01.

08:00 Abgabe der Vortragsfolien und Handoutfolien (siehe unten)
22.01.
23.01.

Individualtermine
02.02. 08:00 Abgabe der Endversionen der Vortragsfolien, der Handoutfolien und der Ausarbeitung, anschließend Druck der Proceedings (incl. Ausarbeitungen und Vortragsfolien).
06.02. ganztägig Blockseminar mit Vorträgen

 

Agenda

Das Blockseminar findet im Ostseejugenddorf Falckenstein statt (Falkenhorst 6, 24159 Kiel-Friedrichsort, Tel.: 0431-7757038) im Raum "Fördeblick". 

Uhrzeit                                           Thema
08:00    Treffen aller Mitfahrer (Uni-Hochhaus)       
08:30    Treffen (Jugenddorf Falckenstein)       
08:45    Andreas Stange                           The aesthetics of graph visualization
09:15    Enno Schwanke                            Graph drawing aesthetics – Created by Users not Algorithms
10:00    Sandra Skrlac                            Memorability of visual features in network diagrams
10:30    Kaffeepause        
10:45    David Gruner                             On the faithfulness of graph visualizations
11:15    Daniel Jahn                              Wellformedness properties in Euler diagrams
11:45    Heiko Brodersen                          Euler diagram generation
12:15    Mittagspause        
14:00    Carsten Sprung                           Drawing graphs in Euler diagrams
14:45    Lasse Folger                             Drawing area-propotional Venn and Euler diagrams
15:15    Mareike Struck                           Untangling Euler diagrams
15:45    Alan Schelten                            Edge compression techniques for visualization of dense directed graphs
16:15    Kaffeepause        
16:30    Lars Peiler                              Semi-automatic editing of graphs with customized layouts
17:00    Lewe Andersen                            Generating customized layouts
17:30    Tibor Weiß                               Applying ant colony optimization metaheuristic to the DAG layering problem
18:00    Rausschmiss        

 

 

Ausarbeitung, Vortrag, Review

Das Seminar beinhaltet die Erstellung einer Ausarbeitung, eines Vortrags, und zweier Reviews.

Die Ausarbeitung soll eine Übersicht über das behandelte Themengebiet darstellen. Sie sollte so verfasst sein, dass sie von einen fortgeschrittenen Bachelor-Informatikstudenten gut verstanden werden kann. Die Ausarbeitung soll 6 (Master/Diplom) bzw. 4 (Bachelor) Seiten umfassen, nicht mehr und nicht weniger, und den ACM LaTeX-Style verwenden. Für mögliche Vorlagen zu den Ausarbeitungen siehe die Proceedings der früheren Seminare. Auch empfehlenswert ist ein Blick in die Hinweise für die Anfertigung einer Abschlussarbeit.

Der Vortrag soll 40 Minuten (Master/Diplom) bzw. 25 Minuten (Bachelor) lang sein. Das Vortragsprogramm wird etwas zusätzliche Zeit für Fragen (5 min) einplanen. Zu dem Vortrag sollen Folien erstellt werden, zum Beispiel mit LaTeX Beamer (siehe unten). Die Vortragsfolien sollten Seitennummern enthalten. Sollte das Thema auch eine konkrete Implementierung behandeln, ist eine entsprechende kurze Tool-Demo im Rahmen des Vortrages sinnvoll. Die Arbeitsgruppe bietet jedem/r Vortragenden an, eine Videoaufnahme des Vortrags zu erstellen und dem/r Vortragenden anschließend zur Verfügung zu stellen.

Ein Review einer Ausarbeitung besteht aus folgenden zwei Komponenten:

  1. Generellen Anmerkungen (was gefällt Ihnen/gefällt Ihnen nicht, zu Inhalt, Gliederung und Lesbarkeit) sowie generelle Verbesserungsvorschläge etc. Mindestens eine halbe Seite, abgegeben als PDF-Datei.
  2. Detaillierteren Korrekturen als elektronisch annotierte PDF-Version der Review-Version der Ausarbeitung. Es empfiehlt sich, hier nur mit dem Adobe Reader zu arbeiten, da Annotationen verschiedener PDF-Viewer oft inkompatibel sind.

Ein eingescannter, handschriftlich annotierter Ausdruck der Ausarbeitung (generelle Anmerkungen sind auch hier erforderlich!) ist notfalls auch ok, wenn gut lesbar, sollte aber vermieden werden. Die Zuordnung Paper/Reviewer geschieht kurzfristig nach dem Abgabetermin für die Review-Versionen der Ausarbeitungen, basierend auf den dann abgegebenen Ausarbeitungen.

Beispiele zur Ausarbeitung und zu Vortragsfolien finden sich in den Proceedings früherer Seminare.

Jede(r) Seminarteilnehmer(in) erhält die Proceedings des laufenden Seminars.

Namenskonventionen

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>/sem14ws-<login>.[tex/pdf]
  • Vortragsfolien: <login>/sem14ws-<login>-talk.[tex/pdf]
  • Handoutfolien - ohne Animationen, für Ausdrucke und die Proceedings: <login>/sem14ws-<login>-handout.[tex/pdf]
  • Review (generelle Anmerkungen): <login review-Empfänger>/sem14ws-<login review-Empfänger>-reviewnotes-<login Reviewer>.[pdf]
  • Review (annotiertes PDF): <login review-Empfänger>/sem14ws-<login review-Empfänger>-review-<login Reviewer>.[pdf] (Beispiel also: Christoph Daniel (cds) reviewt die Ausarbeitung Ulf Rüegg (uru) und checkt das Review-PDF mit dem Namen sem14ss-uru-review-cds.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}").

Benotung

Das Seminar ist benotet. Es werden jeweils Teilnoten für die einzelnen Meilensteine (Versionen der Ausarbeitung, Reviews, Folien, Vortrag) vergeben, aus denen sich die Endnote zusammensetzt. Es werden jeweils die Qualität sowie die Rechtzeitigkeit (siehe Terminplanung) bewertet. Das Nicht-Einhalten von Terminen kann zum Nicht-Bestehen des Seminars führen.

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 Stash 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/14ws-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 sem14ws-<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.

Weiterführende Hinweise / Links

Generell ist es empfehlenswert, aus dem Uni-Netz heraus nach verwandten Publikationen zu suchen, da man hier Zugriff auf einige Online-Blbliotheken bekommt. Zur Suche empfehlen sich folgende Suchmaschinen und Seiten: