Übungen zur Vorlesung "Zeichnen von Graphen"
|
+++ Aktuelles +++ |
Grundlage für die effektive und effiziente Visualisierung von Netzwerken sind Algorithmen zur Bestimmung eines Layouts für den die Netzwerkstruktur beschreibenden Graphen. Das automatische Zeichnen von Graphen hat daher wichtige Anwendungen in Kernbereichen der Informatik wie etwa Datenbanken, Software-Engineering, VLSI- und Netzwerk-Design und visuelle Benutzerschnittstellen. Anwendungen in anderen Bereichen betreffen alle Aspekte der visuellen Datenanalyse, z.B. in den Ingenieurwissenschaften, Chemie und Biologie oder Sozial- und Politikwissenschaft. Dazu werden verschiedene algorithmische Prinzipien und Methoden wie z.B. kräftebasierte Verfahren und Flussmethoden besprochen.
|
Termine
| Vorlesung (U. Brandes) | Di 10:00-11:30 (F 420) Fr 08:30-10:00 (F 420) |
| Übung (C. Pich) | Mo 10:00 - 11:30 (D 247) |
| Klausur | 1. Termin |
| 2. Termin |
Übungsblätter
Übungsblätter werden freitags in der Vorlesung ausgegeben.
Die Aufgaben sind innerhalb einer Woche zu bearbeiten, und werden als schriftliche Ausarbeitungen im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214) abgegeben. Die Besprechung der Aufgaben und die Rückgabe der korrigierten und mit Punkten bewerteten Abgaben erfolgt in der Übung. Das Erlangen von mindestens der Hälfte der möglichen Punkte und die aktive Teilnahme an den Übungen ist Voraussetzung für die Zulassung zur Klausur.
Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.
| Nr. | Ausgabe | Abgabe | Besprechung | Download |
|---|---|---|---|---|
| 1 | 28.04.2006 | 05.05.2006 | 08.05.2006 | |
| 2 | 05.05.2006 | 12.05.2006 | 15.05.2006 | |
| 3 | 12.05.2006 | 19.05.2006 | 22.05.2006 | PDF (zu Aufg. 8 PDF) |
| 4 | 19.05.2006 | 26.05.2006 | 29.05.2006 | PDF (zu Aufg. 11 PDF) |
| 5 | 26.05.2006 | 02.06.2006 | 12.06.2006 | |
| 6 | 02.06.2006 | 09.06.2006 | 12.06.2006 | |
| 7 | 09.06.2006 | 16.06.2006 | 19.06.2006 | |
| 8 | 16.06.2006 | 23.06.2006 | 26.06.2006 | |
| 9 | 23.06.2006 | 30.06.2006 | 03.07.2006 | |
| 10 | 30.06.2006 | 07.07.2006 | 10.07.2006 | PDF (Beispielgraph YGF) |
| 11 | 07.07.2006 | 14.07.2006 | 17.07.2006 | |
| 12 | 14.07.2006 | 21.07.2006 | 24.07.2006 | |
| 13 | 21.07.2006 | keine | keine |
Hinweis: Einige Dokumente sind nur lokal lesbar.
Praktische Aufgaben
Für die praktischen Aufgaben wird die Bibliothek yFiles verwendet. Die Lösungen sind als Quellcode per Email zu versenden und der Abgabe als Papierversion beizufügen.
- Einführung in die Programmierumgebung aus dem Projektpraktikum Sensor- und Ad Hoc-Netzwerke (WS 2005/2006)
- yFiles Developer's Guide
- yFiles-Beispiele, für Anfänger v.a. interessant: Base Demos
- yFiles 2.4.0.1 API Documentation
Skriptum
Grundlage ist das Skript der Veranstaltung im Sommersemester 2004. Dieses wird im Verlauf des Semesters ergänzt und überarbeitet. Für Anmerkungen und Hinweise auf Fehler sind wir dankbar.
- Kurzskripte zu Grundlagen
- Kapitel 1 aus dem Skriptum zur Vorlesung "Entwurf und Analyse von Algorithmen" von Prof. Wagner über Rekursion
- Originalartikel zum Verfahren für die x-Koordinatenzuweisung im Sugiyama-Ansatz
Literatur
- G. Di Battista, P. Eades, I.G. Tollis, R. Tamassia: "Graph Drawing: Algorithms for the Visualization of Graphs". Prentice Hall, 1999
- M. Jünger, P. Mutzel (Eds.): "Graph Drawing Software" Mathematics and Visualization Series, Springer-Verlag, 2003
- M. Kaufmann, D. Wagner (Eds.): "Drawing Graphs -- Methods and Models". Lecture Notes in Computer Science Tutorial 2025, Springer-Verlag 2001
- K. Sugiyama: "Graph Drawing and Applications for Software and Knowledge Engineers". World Scientific, 2002
Weitere Informationen
- Eintrag im Vorlesungsverzeichnis
- Informationen zum Account-Tool
- Java Demo Applet (Spring Embedder)
- Anwendungsbeispiele für das Zeichnen von Graphen
- Konferenz: Graph Drawing 2006 (mit Wettbewerb zum Thema Graphenzeichnen)