LTI
LTI

Proseminar: Graph Drawing

  • Leitung:
    Prof. Dr. Harald Räcke
  • Modul: IN0013, TUMonline
  • Bereich:
    2 SWS Proseminar im Bereich Informatik III (Theoretische Informatik)
  • Anmeldung:
    Für die Anmeldung muss der Student sich mit der Seminarleitung in Verbindung setzen. Die Studenten, die ein Thema bekommen haben, werden dann von der Seminarleitung in TUMonline angemeldet. Wer sicher einen Platz erhalten möchte, sollte zur Vorbesprechung erscheinen, da die dort erscheinenden Personen priorisiert werden. Falls ihr Interesse habt, meldet euch bitte zusätzlich kurz bei Harald Räcke (raecke@in.tum.de), damit die Teilnehmerzahl besser abgeschätzt werden kann.
  • Vorbesprechung:
    Montag, 27.1.2014; 13:00-14:00 im Seminarraum MI 03.11.018
  • Zeit:
  • Schein:
    Einen Seminarschein erhält, wer einen Vortrag gehalten, eine Ausarbeitung geschrieben und regelmäßig aktiv am Seminar teilgenommen hat.
  • Hörerkreis:
    Studierende im Grundstudium der Informatik
    Studierende im Bachelorstudiengang Informatik
    Studierende mit Nebenfach Informatik
  • Voraussetzungen:
    Voraussetzung für die Teilnahme am Proseminar sind neben Interesse an Algorithmen, auch Englischkenntnisse, die ausreichend für die Bearbeitung der ausschließlich englischsprachigen Literatur sein müssen.

Zusammenfassung

Zeichnungen mit versch. Kurventypen Das Ziel eines Proseminar ist einerseits die vertieften inhaltlichen Auseinandersetzung mit einem Thema. Andererseits dient ein Proseminar aber auch dazu, die Fähigkeiten im Ausarbeiten und Halten von Vorträgen zu verbessern, und wir werden versuchen, Sie dabei zu unterstützen. Dazu gehören aus aktuellem Anlass auch die Grundlagen wissenschaftlichen Arbeitens, beispielsweise das korrekte Zitieren.

Das Visualisieren struktureller Information ist für das Verständnis komplexer Zusammenhänge von entscheidender Bedeutung. Beispiele in der Informatik sind das Visualisieren von Datenbankmodellen in CASE-Tools, eine graphische Darstellung der Zustandsübergänge bei Automaten oder das Data-Mining. Graphen sind ein ideales Hilfsmittel, um strukturelle Information abstrakt zu modellieren. Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten. Eine Kante verläuft dabei zwischen zwei Knoten und beschreibt eine Beziehung zwischen diesen Knoten.

Eine Zeichnung eines Graphen ist eine Darstellung dieser Beziehungen als Diagramm. Sie ordnet den Knoten Symbole (etwa Kreise oder Rechtecke) und Koordinaten (meist in der euklidischen Ebene) zu. Die Kanten werden durch Kurven zwischen den zugehörigen Knotensymbolen dargestellt. Beispiele für erlaubte Kurven sind Polygonzüge, orthogonale Polygonzüge oder Geradensegmente.

2 ästhetische Kriterien Graphenzeichnungen sollen vor allem zwei Anforderungen genügen: Sie sollen "schön" sein, aber auch die strukturellen Zusammenhänge der zugrundeliegenden Daten herausarbeiten. Es ist klar, dass manche Zeichnungen die enthaltene Information besser zum Ausdruck bringen als andere. Deshalb werden ästhetische Kriterien festgelegt, welche die Lesbarkeit von Graphen erhöhen sollen. Man kann etwa verlangen, dass Symmetrien oder Cluster in einem Graphen sichtbar werden oder dass die Anzahl der Schnittpunkte von Kanten möglichst klein ist. Diese Kriterien sind jedoch subjektiv und kontextabhängig. Sind die Anforderungen an die Darstellung einer Klasse von Graphen einmal festgelegt, dann versucht man, effiziente Algorithmen zu entwickeln, die möglichst gute Zeichnungen automatisch liefern.

Level-Zeichnung eines Binärbaumes In diesem Proseminar sollen in den einzelnen Vorträgen grundlegende Ergebnisse aus diesem aktiven Forschungsgebiet vorgestellt werden. Es werden zuerst Algorithmen für das Zeichnen von Bäumen untersucht. Dann wird der Frage nachgegangen, wann sich ein Graph ohne Überschneidungen von Kanten zeichnen lässt. Für den Fall, dass letzteres nicht möglich ist, werden Algorithmen angewendet, die die Zahl der Kantenkreuzungen zumindest klein halten. Neben einigen weiteren Graphklassen und -algorithmen werden zudem aktuelle Anwendungen vorgestellt.

Mögliche Themen

  1. Einführung: Wie zeichnet man einen Graphen? [1,2,3,4]
  2. Schöne Zeichnungen von Bäumen [5,6,19]
  3. Zeichnungen von Binärbäumen mit optimaler Fläche [7,19]
  4. Zeichnungen in mehreren Ebenen [8,19]
  5. Das Feder-Modell zum Zeichnen beliebiger Graphen [9,19]
  6. Hierarchische Zeichnungen [10,19]
  7. Testen eines Graphen auf Planarität [11,12,19]
  8. Ein einfacher Algorithmus für das Zeichnen planarer Graphen [1,13]
  9. Planarisierung von Graphen [1,14,19]
  10. Färben von Landkarten (planare Graphen) [15,16]
  11. Minimierung von Kantenkreuzungen bei allgemeinen Graphen [19]
  12. 3-D Zeichnungen von Graphen [17,18,19]
(Die Angaben in eckigen Klammern beziehen sich auf die Nummern in der Literaturliste.)

Literatur

  1. P. Eades, P. Mutzel: Graph drawing algorithms. In Mikhail J. Atallah, editor, Algorithms and Theory of Computation Handbook, Chapter 9, CRC Press, Boca Raton, 1999.
  2. G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph drawing. Upper Saddle River, NJ, Prentice Hall, pp. 1–18,1999.
  3. I.F. Cruz, R. Tamassia: How to visualize a graph: specifications and algorithms. Tutorial, 1994.
  4. R. Tamassia: Graph drawing. In Eli Goodman and Joseph O’Rourke, editors, Handbook of Discrete and Computational Geometry, Chapter 44, CRC Press, Boca Raton, 1999.
  5. C. Wetherell and A. Shannon: Tidy drawing of trees. IEEE Trans. on Software Engineering, Vol. SE-5(5), pp. 514–520, 1979.
  6. E.M. Reingold, J.S. Tilford: Tidier drawing of trees. IEEE Trans. on Software Engineering, Vol. SE-7(2), pp. 223–228, 1981.
  7. P. Crescenzi, G. Di Battista, A. Piperno: A note on optimal area algorithms for upward drawings of binary trees. Computational Geometry: Theory and Applications, Vol. 2, pp. 187–200, 1992.
  8. K. Sugiyama, S. Tagawa, and M. Toda: Methods for visual understanding of hierarchical system structures. IEEE Trans. on Systems, Man, and Cybernetics, SMC-11(2), pp. 109–125, 1981.
  9. T.M.J. Fruchterman, E.M. Reingold: Graph drawing by force-directed placement. Software–Practice and Experience, Vol. 21(11), pp. 1129–1164, 1991.
  10. P. Eades, M.L. Huang: Navigating clustered graphs using force-directed methods. Journal of Graph Algorithms and Applications, Vol. 4(3), pp. 157–181, 2000.
  11. A. Gibbons: Planar graphs. In Algorithmic Graph Theory, Chapter 3, pp. 67–95. Press Synicate of the University of Cambridge, Cambridge, New York, Melbourne, 1985, Reprint 1991.
  12. R. Thomas: Planarity in linear time. Class notes, 1997.
  13. R. Read: A new method for drawing a planar graph given the cyclic order of the edges at each vertex. Congressus Numerantium, Vol. 56, pp. 31–44, 1987.
  14. P. Eades, L. Foulds, J. Giffin: An efficient heuristic for identifying a maximal weight planar subgraph. Combinatorial Mathematics IX, Lecture Notes in Mathematics, Vol. 952, pp. 239–251, 1982.
  15. M. Aigner, G.M. Ziegler: Proofs from THE BOOK. Springer, Berlin, Chapter 25 1998.
  16. D.B. West: Introduction to graph theory. Prentice Hall, Upper Saddle River, NJ, Chapter 7.1 and 7.3, 1996.
  17. P. Eades, C. Stirk, S. Whitesides: The techniques of Kolmogorov and Bardzin for three dimensional orthogonal graph drawing. Information Processing Letters, 60(2), pp. 97–103, 1996.
  18. G. Di Battista, M. Patrignani, F. Vargiu: A split&push approach to 3D orthogonal drawing. In Proceedings of the 6th International Symposium on Graph Drawing (GD'98), Ed. Whitesides, Berlin, Springer, pp. 87–101, 1998.
  19. R. Tamassia: Handbook of Graph Drawing and Visualization, CRC Press

Gute Vorträge

An dieser Stelle wollen wir ein paar Hinweise zum Vorbereiten und Halten guter Präsentationen zusammenfassen. Falls Sie eine weitere gute Beschreibung finden, können Sie diese bitte gerne Johannes Krugel mitteilen.
  • Hilfreiche Hinweise zur Vorbereitung, zum Erstellen der Folien und zum eigentlichen Vortrag geben Garr Reynolds' presentation tips.
  • Einige sehr wichtige Aspekte guter Vorträge sind auch im Beamer User Guide in Kapitel I.5 Guidelines for Creating Presentations beschrieben.
  • Die Fokussierung auf eine wichtige Nachricht wird in der kurzen Präsentation Rethinking Presentation Design betont.
  • Bei einigen Themen bietet es sich möglicherweise an, den Algorithmus in einer kurzen Live-Demonstration vorzuführen (z. B. per Java-Applet). Falls Sie einen der Algorithmen selbst programmieren möchten, können Sie dafür beispielsweise die LEDA-Softwarebibliothek verwenden. Weitere Informationen dazu finden Sie auf der Webseite von unserem Praktikum Algorithmen-Entwurf unter Aufgaben.

Hinweise

Vorbereitung
Jeder Studierende wählt ein Thema, sucht sich relevante Literatur und verschafft sich einen Überblick über das Thema. Anschließend wird der Entwurf der Präsentation erstellt, dies beinhaltet beispielsweise das Erstellen der Folien und die Planung des Tafelbilds.
Vorbesprechung
Spätestens zwei Wochen vor dem Vortragstermin wird der Entwurf des Vortrags mit dem jeweiligen Betreuer durchgesprochen. Dazu vereinbart jeder Studierende rechtzeitig einen Termin. Zu diesem Zeitpunkt muss auch mindestens die Gliederung der Ausarbeitung vorliegen.
Probevortrag
Beim Probevortrag präsentiert jeder Studierende sein Thema einem Kommilitonen, der dann dazu konstruktive Kritik äußert (spätestens eine Woche vor dem eigentlichen Vortrag).
Seminarvortrag
Der Seminarvortrag dauert 45 ± 5 Minuten. Nach dem Vortrag hat das Publikum die Möglichkeit, Fragen zu stellen. Eine LaTeX-Vorlage für die Präsentation findet sich in diesem Ordner. Eine Powerpoint-Vorlage kann man auf der Seite vom TUM Corporate Design herunterladen (Login mit MyTUM-Kennung). Diese Vorlagen müssen nicht verwendet werden oder können bei Bedarf auch angepasst werden.
Seminararbeit
Eine erste Version der Ausarbeitung wird einem Kommilitonen zur Verfügung gestellt, der dann eine kurze Kritiken schreibt. Die Endfassung der Seminarbeit ist als PDF-Datei abzugeben. Der Umfang der Seminararbeit beträgt 6 ± 1 Seiten (ohne Inhalts- und Literaturverzeichnis). Eine LaTeX-Vorlage für die Ausarbeitung findet sich in diesem Ordner (die Verwendung dieser Vorlage ist obligatorisch).


Anwesenheit
Jeder Studierende muss bei allen Vorträgen anwesend sein und sich aktiv an der Diskussion beteiligen.
Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail