Real-Time and Embedded Systems

Seminar Layout-Algorithmen für Graphen WS'11

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

Proceedings

Voraussetzungen:

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

Dozenten:

Reinhard v. Hanxleden (rvh), Miro Spönemann (msp)

Termine:

Do, 7.7. 10:15 Uhr, Ü3 Erste Vorbesprechung
Mi, 26.10. 9:45 Uhr, Ü1 Zweite Vorbesprechung, Kick-Off
Mo, 31.10.   Frist für Themenauswahl (per Mail an Dozenten)
Mo, 31.10. 18:00 Uhr, Ü1 LaTeX / SVN Kurzeinführung
Mo, 14.11. 12:00 Uhr Abgabe Ausarbeitungsgerüst (Abstract, Einleitung, Gliederung, Stichworte, Bibliographie)
Di, 15.11. R1117 Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Mo, 19.12. 12:00 Uhr Abgabe Erstversion der vollständigen Ausarbeitung
Di, 20.12. R1117 Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Mo, 9.1. 12:00 Uhr Abgabe Vortragsfolien und Handoutfolien (siehe unten)
Di, 10.1. R1117 Individualtermine, für Terminabsprache bitte Dozenten ansprechen
Mo, 16.1. 12:00 Uhr Abgabe der Review-Version der Ausarbeitung
Mo, 16.1. 18:00 Uhr Zuordnung Ausarbeitungen/Reviewer (per E-Mail)
Mo, 23.1. 12:00 Uhr Abgabe der Reviews
Mo, 30.1. 12:00 Uhr Abgabe der Endversion der Vortragsfolien und der Ausarbeitung, anschließend Druck der Proceedings (incl. Ausarbeitungen und Vortragsfolien).
Mo, 6.2.   Blockseminar mit Vorträgen (Programm siehe unten)

 

Themenzuordnung / Programm des Blockseminars am 6.2.2012

Zeit Teilnehmer Thema
8:00 Nicht-Selbstfahrer Treffen vor dem Unihochhaus, Abfahrt
8:30 Alle Treffen Jugenddorf Falckenstein (Falkenhorst 6, 24159 Kiel)
8:55 Dozenten Begrüßung/Einleitung
9:00 Tomke Reibisch How Important Is the “Mental Map”?
9:30 Andreas Boysen Graph Layout for Displaying Data Structures
10:00 Patrick Günther Horizontal Coordinate Assignment
10:30 Kaffeepause  
10:45 Gregor Hoops Crossing Reduction for Orthogonal Circuit Visualization
11:30 Stanislaw Nasin Orthogonal Connector Routing
12:00 Heiko Wissmann Inserting an Edge into a Planar Graph
12:30 Mittagspause Evt. Strandspaziergang (Schuhwerk/Badezeug)
14:00 Dennis Brunsch Bend Minimization in the Kandinsky Model
14:30 Matthias Nannt Compaction for Orthogonal Drawings
15:00 Sandra Dylus Level Planarity Testing and Layout with Embedding Constraints
15:30 Kaffeepause  
15:45 Paul Klose Fast Node Overlap Removal
16:30 Jens-Uwe Bahr Integrating Edge Routing into Force-Directed Layout
17:00 Kevin Hesse Grammar-Based Layout
17:30 Dozenten 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 freigeschaltet sind.

  1. C. Gutwenger, P. Mutzel, R. Weiskircher, Inserting an edge into a planar graph, Algorithmica 41(4), pp. 289-308, Springer, 2005. [pdf]
  2. U. Brandes, B. Köpf, Fast and simple horizontal coordinate assignment, Proceedings of the 9th International Symposium on Graph Drawing, vol. 2265 of LNCS, pp. 31-44, Springer, 2002. [pdf]
  3. T. Eschbach, W. Günther, B. Becker, Crossing reduction for orthogonal circuit visualization, Proceedings of the International Conference on VLSI, pp. 107-113, CSREA Press, 2003. [pdf]
  4. W. Barth, P. Mutzel, C. Yıldız, A new approximation algorithm for bend minimization in the Kandinsky model, Proceedings of the 14th International Symposium on Graph Drawing, vol. 4372 of LNCS, pp. 343-354, Springer, 2007. [pdf]
  5. M. Eiglsperger, M. Kaufmann, Fast compaction for orthogonal drawings with vertices of prescribed size, Proceedings of the 9th International Symposium on Graph Drawing, vol. 2265 of LNCS, pp. 67-71, Springer, 2002. [pdf]
  6. G. Gange, P.J. Stuckey, K. 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. [pdf]
  7. M. Wybrow, K. Marriott, P.J. Stuckey, Orthogonal connector routing, Proceedings of the 17th International Symposium on Graph Drawing, vol. 5849 of LNCS, pp. 219-231, Springer, 2010. [pdf]
  8. M. Harrigan, P. Healy, Practical Level Planarity Testing and Layout with Embedding Constraints, Proceedings of the 15th International Symposium on Graph Drawing, vol. 4875 of LNCS, pp. 62-68, Springer, 2008. [pdf]
  9. T. Dwyer, K. Marriott, M. Wybrow, Integrating Edge Routing into Force-Directed Layout, Proceedings of the 14th International Symposium on Graph Drawing, vol. 4372 of LNCS, pp. 8-19, Springer, 2007. [pdf]
  10. H. Purchase, E. Hoggan, C. Görg, How Important Is the “Mental Map”? – An Empirical Investigation of a Dynamic Graph Layout Algorithm, Proceedings of the 14th International Symposium on Graph Drawing, vol. 4372 of LNCS, pp. 184-195, Springer, 2007. [pdf]
  11. T. Dwyer, K. Marriott, P.J. Stuckey, Fast Node Overlap Removal. Proceedings of the 13th International Symposium on Graph Drawing, vol. 3843 of LNCS, pp. 153-164, Springer, 2006. [pdf]
  12. J.M. Six, I.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. [pdf]
  13. K.-B. Zhang, K. Zhang, M.A. Orgun, Grammar-Based Layout for a Visual Programming Language Generation System. Proceedings of the Second International Conference on Diagrammatic Representation and Inference, vol. 2317 of LNCS, pp. 559-572, Springer, 2002. [pdf]
  14. V. Waddle, Graph Layout for Displaying Data Structures. Proceedings of the 8th International Symposium on Graph Drawing, vol. 1984 of LNCS, pp. 98-103, Springer, 2001. [pdf]
  15. P. Griebel, G. Lehrenfeld, W. Mueller, C. Tahedl, H. Uhr, Integrating a Constraint Solver into a Real-Time Animation Environment. Proceedings of the IEEE Symposium on Visual Languages, pp. 12-19, IEEE, 1996. [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 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 einer elektronisch (z.B. mit Xournal) annotierten PDF-Version der Review-Version der Ausarbeitung. Die Annotationen bestehen aus:

  1. Generellen Anmerkungen (mind. 1/2 Seite) - was gefällt Ihnen/gefällt Ihnen nicht, zu Inhalt, Gliederung, Lesbarkeit, sowie generellen Verbesserungsvorschläge etc., z.B. als Textbox am Anfang des PDFs eingefügt, und
  2. Detaillierteren Korrekturen.

Ein eingescannter, handschriftlich annotierter Ausdruck der Ausarbeitung ist notfalls auch ok, sollte aber vermieden werden. Sollten Sie einen Scanner benötigen und keinen zur Verfügung haben, wenden Sie sich bitte an das Sekretariat der Arbeitsgruppe. 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. Das Review zu einer Ausarbeitung soll direkt im Zielordner des Autors der Ausarbeitung abgelegt werden. 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 SVN 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: .../teaching/sem/11ws-layout/<login>/sem11ws-<login>.[tex/pdf]
  • Vortragsfolien: .../11ws-layout/<login>/sem11ws-<login>-talk.[tex/pdf]
  • Handoutfolien - ohne Animationen, für Ausdrucke und die Proceedings: .../11ws-layout/<login>/sem11ws-<login>-handout.[tex/pdf]
  • Review: .../11ws-layout/<login>/sem11ws-<login>-review-<reviewer-login>.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}").

Weiterhin: Die Reviews sollten vom Autor der Reviews im Verzeichnis der begutachteten Ausarbeitung eingecheckt werden. Also, <reviewer-login> checkt das von <reviewer-login> erstellte Review für die Ausarbeitung von <login> in .../11ws-layout/<login>/sem11ws-<login>-review-<reviewer-login>.pdf ein, und schickt an <login> eine kurze E-Mail mit einem entsprechenden Hinweis, mit CC an den Dozenten.

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. Letztlich zählt für die Note also nicht nur das endgültige Resultat (Ausarbeitung/Vortrag) sondern auch der gesamte Prozess, aus dem jenes hervorgegangen ist.

Technisches

  • Subversion Repository auschecken: svn co http://rtsys.informatik.uni-kiel.de/svn/teaching/sem/11ws-layout/
  • 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 (innerhalb des rtsys-Netzwerks auch global verfügbar). Im SVN befinden sich in .../11ws-layout/init/ eine Reihe von Dateien (incl. README.txt), welche Sie als Template nehmen können.
  • 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