Real-Time and Embedded Systems

Seminar Layout-Algorithmen für Graphen SS'13

Sinn dieses Seminars ist es, sich mit einem Themengebiet 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 praktizieren, 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 (Inf-Sem-Echtz, Univis-Eintrag, Modulbeschreibung) und als Master/Diplom-Modul (MSS1101, Univis-Eintrag, Modulbeschreibung). 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), Miro Spönemann (msp), Christoph Daniel Schulze (cds)

Termine:

Mi. 10.4. 10:15 Uhr, Ü2 Vorbesprechung für Master-Studierende
Fr. 12.4.   Frist für Themenauswahl (per Mail an Dozenten)
Di. 16.4. 10:00 Uhr, CAP4 R.715 LaTeX / Git Kurzeinführung
Do. 25.4. 12:00 Uhr Abgabe Ausarbeitungsgerüst (Abstract, Einleitung, Gliederung, Stichworte, Bibliographie)
Fr. 26.4.   Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Do. 16.5. 12:00 Uhr Abgabe Erstversion der vollständigen Ausarbeitung
Fr. 17.5.   Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Do. 23.5. 12:00 Uhr Abgabe Vortragsfolien und Handoutfolien (siehe unten)
Fr. 24.5.   Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Do. 30.5. 12:00 Uhr Abgabe der Review-Version der Ausarbeitung
Do. 30.5.   Zuordnung Ausarbeitungen/Reviewer (per E-Mail)
Do. 6.6. 12:00 Uhr Abgabe der Reviews
Mi. 19.6. 12:00 Uhr Abgabe der Endversion der Vortragsfolien und der Ausarbeitung, anschließend Druck der Proceedings (incl. Ausarbeitungen und Vortragsfolien).
Fr. 21.6. Friedrichsort Blockseminar mit Vorträgen (Programm siehe unten)

Proceedings

Download der Seminarausarbeitungen:mit Vortragsfolien

Agenda

Das Blockseminar am 21.6. wird der folgenden Agenda folgen:

Zeit Mensch Thema
08:00 Alle Mitfahrer Treffen (Foyer Uni-Hochhaus)
08:30 Alle Treffen (Jugenddorf Falckenstein)
08:55 Dozenten Begrüßung
09:00 Astrid Mariana Flohr An efficient implementation of Sugiyama's algorithm for layered graph drawing
09:30 Thorge Petersen Optimal k-level planarization and crossing minimization
10:00 Thomas Rossow Improving layered graph layouts with edge bundling
10:30 Katja Petrat An evolutionary algorithm for drawing directed graphs
11:00   Kaffeepause
11:15 Oliver Kwast Interactive random graph generation with evolutionary algorithms
11:45 Julia Kunst Optical graph recognition
12:15   Mittagspause
13:45 Dennis Trümper A framework for circular drawing of networks
14:15 Martin Schröder Mental map preservation helps user orientation in dynamic graphs
14:45   Kaffeepause
15:00 Daniel Grevismühl Drawing graphs on a smartphone
15:30 Malte Hecht Dynamic map labeling
16:00   Kaffeepause
16:15 Bastian Holst Smooth orthogonal layouts
17:00 Florian Biß Evaluating partially drawn links for directed graph edges
17:30   Schlussworte

Seminarthema

Eingebettete Echtzeitsysteme werden sehr häufig mittels graphischer domänenspezifischer Modellierungssprachen entwickelt, besonders wenn damit, wie im Fahrzeug- oder Flugzeugbau, sicherheitskritische Aspekte oder eine hohe Komplexität verbunden sind. Zur Unterstützung des modellbasierten Entwurfsprozesses werden Transformationen zwischen verschiedenen Formen eines Modells eingesetzt, was die automatische Generierung von graphischen Sichten für das Modell voraussetzt. Da die meisten Modelle strukturell auf Graphen basieren, können hier Layout-Algorithmen für Graphen verwendet werden. Mit diesem Hintergrund ist das Thema dieses Seminars die Recherche und Diskussion von Ansätzen, Algorithmen und Optimierungsmethoden für die automatische Anordnung von Graphen auf einer zweidimensionalen Ebene. Inhaltlich geht es hierbei um Ästhetikkriterien, Graphentheorie, Optimierungsprobleme und die Entwicklung von Heuristiken.

Grundlagen

Zur Einführung in die Thematik empfehlen wir folgende Bücher.

  • G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, New Jersey, 1999.
  • M. Kaufmann, D. Wagner (Editors), Drawing Graphs: Methods and Models, Springer-Verlag, Berlin, Heidelberg, 2001.
  • M. Jünger, P. Mutzel (Editors), Graph Drawing Software, Springer-Verlag, Berlin, Heidelberg, 2004.

Ein Teil der Seminararbeit ist eine eigenständige Literaturrecherche (s. dazu Abschnitt ''Weiterführende Hinweise/Links''). Diese sollte auf ein konkretes Thema ausgerichtet sein, was Sie selbst vorschlagen oder aus folgenden Veröffentlichungen wählen können. Beachten Sie, dass einige PDFs nur innerhalb des Universitäts-Netzwerks kostenlos zugänglich sind.

  1. Janet M. Six, Ioannis G. Tollis, A framework for circular drawings of networks, Proceedings of the 7th International Symposium on Graph Drawing, vol. 1731 of LNCS, pp. 107-116, Springer, 1999 (vergeben an Dennis Trümper) pdf
  2. Sonja Maier, Mark Minas, A pattern-based layout algorithm for diagram editors, Proceedings of the Workshop on the Layout of (Software) Engineering Diagrams, vol. 7 of Electronic Communications of the EASST, 2007 pdf
  3. Sabine Cornelsen, Andreas Karrenbauer, Accelerated bend minmization, Proceedings of the 19th International Symposium on Graph Drawing, vol. 7034 of LNCS, pp. 111-122, Springer, 2012 (vergeben an Christian Schoen) pdf
  4. Markus Eiglsperger, Martin Siebenhaller, Michael Kaufmann, An efficient implementation of Sugiyama's algorithm for layered graph drawing, Proceedings of the 12th International Symposium on Graph Drawing, vol. 3383 of LNCS, pp. 155-166, Springer, 2005 (vergeben an Astrid Mariana Flohr) pdf
  5. J. Utech, J. Branke, H. Schmeck, P. Eades, An evolutionary algorithm for drawing directed graphs, Proceedings of the International Conference on Imaging Science, Systems and Technology, pp. 154-160, 1998 (vergeben an Katja Petrat) pdf
  6. Daniel Archambault, Helen C. Purchase, Bruno Pinaud, Difference map readability for dynamic graphs, Proceedings of the 18th International Symposium on Graph Drawing, vol. 6502 of LNCS, pp. 50-61, Springer, 2011 (vergeben an Kannan Thambia) pdf
  7. Giordano Da Lozzo, Giuseppe Di Battista, Francesco Ingrassia, Drawing graphs on a smartphone, Proceedings of the 18th International Symposium on Graph Drawing, vol. 6502 of LNCS, pp. 153-164, Springer, 2011 (vergeben an Daniel Grevismüh) pdf
  8. Ken Been, Eli Daiches, Chee Yap, Dynamic map labeling, vol. 12(5) of IEEE Transactions on Visualization and Computer Graphics, pp. 773-780, 2006 (vergeben an Malte Hecht) pdf
  9. Michael Burch, Corinna Vehlow, Natalia Konevtsova, Daniel Weiskopf, Evaluating partially drawn links for directed graph edges, Proceedings of the 19th International Symposium on Graph Drawing, vol. 7034 of LNCS, pp. 226-237, Springer, 2012 (vergeben an Florian Biß) pdf
  10. Sergey Pupyrev, Lev Nachmanson, Michael Kaufmann, Improving layered graph layouts with edge bundling, Proceedings of the 18th International Symposium on Graph Drawing, vol. 6502 of LNCS, pp. 329-340, Springer, 2011 (vergeben an Thomas Rossow) pdf
  11. Stephen C. North, Incremental layout in DynaDAG, Proceedings of the Symposium on Graph Drawing, vol. 1027 of LNCS, pp. 409-418, Springer, 1996 pdf
  12. Benjamin Bach, André Spritzer, Evelyne Lutton, Jean-Daniel Fekete, Interactive random graph generation with evolutionary algorithms, Proceedings of the 20th International Symposium on Graph Drawing, vol. 7704 of LNCS, pp. 541-552, Springer, 2013 (vergeben an Oliver Kwast) pdf
  13. Daniel Archambault, Helen C. Purchase, Mental map preservation helps user orientation in dynamic graphs, Proceedings of the 20th International Symposium on Graph Drawing, vol. 7704 of LNCS, pp. 475-486, Springer, 2013 (vergeben an Martin Schröder) pdf
  14. Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Josef Reislhuber, Optical graph recognition, Proceedings of the 20th International Symposium on Graph Drawing, vol. 7704 of LNCS, pp. 529-540, Springer, 2013 (vergeben an Julia Kunst) pdf
  15. Graeme Gange, Peter J. Stuckey, Kim Marriott, Optimal k-level planarization and crossing minimization, Proceedings of the 18th International Symposium on Graph Drawing, vol. 6502 of LNCS, pp. 238-249, Springer, 2011 (vergeben an Florian Mai) pdf
  16. Michael A. Bekos, Michael Kaufmann, Stephen G. Kobourov, Antonios Symvonis, Smooth orthogonal layouts, Proceedings of the 20th International Symposium on Graph Drawing, vol. 7704 of LNCS, pp. 150-161, Springer, 2013 (vergeben an Bastian Holst) pdf

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 aussagekräftige Folien erstellt werden, 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 einem handschriftlich annotierten Ausdruck zusammen mit einem Blatt mit generellen Anmerkungen:

  • Drucken Sie die Ihnen zugeordneten Ausarbeitungen aus und schreiben Sie darin Korrekturen von Rechtschreibung und Ausdruck sowie weitere Anmerkungen zu konkreten Teilen des Papers.
  • Schreiben Sie mit LaTeX, OpenOffice o.ä. mind. 1/2 Seite mit generellen Anmerkungen - was gefällt Ihnen/gefällt Ihnen nicht zu Inhalt, Gliederung, Lesbarkeit etc. und geben Sie wo zutreffend Verbesserungsvorschläge an. Fügen Sie dieses Blatt in ausgedruckter Form dem Ausdruck mit handschriftlichen Anmerkungen bei.

Die Reviews sollten anonym gestaltet werden, geben Sie also nicht Ihren Namen an. Auf Anfrage können wir Dokumente in unserer Arbeitsgruppe ausdrucken. Die Zuordnung Paper/Reviewer geschieht kurzfristig nach dem Abgabetermin für die Review-Versionen der Ausarbeitungen, basierend auf den dann abgegebenen Ausarbeitungen.

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>/sem13ss-<login>.[tex/pdf]
  • Vortragsfolien: <login>/sem13ss-<login>-talk.[tex/pdf]
  • Handoutfolien - ohne Animationen, für Ausdrucke und die Proceedings: <login>/sem13ss-<login>-handout.[tex/pdf]

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 ist eine Registrierung in Stash erforderlich. Danach muss einer der Seminarverantwortlichen benachrichtigt werden, damit die Zugriffsrechte eingerichtet werden können.
  • Git-Repository auschecken: git clone ssh://git@git.rtsys.informatik.uni-kiel.de:7999/SEM/13ss-layout.git
    • Um die Erstellung der Proceedings zu erleichtern, richten Sie sich bitte nach den oben beschriebenen Namenskonventionen.
  • Texlipse Latex Eclipse Plugin: http://texlipse.sourceforge.net/
    • URL kann direkt als Eclipse update site benutzt werden
    • Bei der Erstellung eines neuen Texlipse Projektes im New-Wizard auf pdf als Ausgabeformat umstellen und pdflatex benutzen (siehe unten)
  • 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!)
    • Texlipse unterstützt ein sehr ausführliches "figure" template (irgendwo figure tippen und Strg-Leertaste drücken)
    • Von der Kommandozeile aus kann ein pdf mit "rubber -d sem11ws-<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.

    • Texlipse ruft pdflatex und bibtex in den richtigen Reihenfolgen automatisch auf.
    • Texlipse unterstützt sehr schöne Templates und Autovervollständigung für Bibliographie: Im *.bib file "@" tippen und Strg+Leertaste drücken, dann bekommt man eine Auswahl aller möglichen Bibliographielemente angezeigt. Entsprechend im .tex-File "\cite{}" Tippen, dort öffnet die Autovervollständigung eine Liste aller vorhandenen bib-Einträge

Weiterführende Hinweise / Links