Wintersemester 2017/18

Algorithmen zur Visualisierung von Graphen

Günter Rote, Boris Klemz

Vorlesungs- und Übungstermine:

Vorlesungen:

Dienstag, 14:15 Uhr bis 15:45 Uhr im Seminarraum 051, Takustraße 9. Beginn: 17.10.2017
Freitag, 10.15 Uhr bis 11:45 Uhr im Seminarraum 053, Takustraße 9

Übungen:

Mittwoch, 14:15 Uhr bis 15:45 Uhr im Seminarraum 051, Takustraße 9. Beginn: 25.10.2017

Anmeldung:

Bitte melden Sie sich im KVV-System zur Vorlesung und zu den Übungsgruppen an. Melden Sie sich auch im Campus-Management-System an, damit Ihnen Ihre Leistungen bescheinigt werden können.

Literatur:

Graph Drawing: Algorithms for the Visualization of Graphs, Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis
Prentice-Hall, 1999, ISBN: 0-13-301615-3
Planar Graph Drawing, Takao Nishizeki, Md. Saidur Rahman
World Scientific, 2004, ISBN: 981-256-033-5
Drawing Graphs: Methods and Models, Michael Kaufmann, Dorothea Wagner (Hrsg.)
Springer, 2001, ISBN: 3-540-42062-2

Übungen:

Die Übungszettel werden ausschließlich online erscheinen, und zwar hier auf dieser Seite. Die Bearbeitungsdauer reicht gewöhnlich von von Freitag bis zum Freitag der nächsten Woche vor der Vorlesung (10:15 Uhr), also 7 Tage. Verspätet abgegebene Übungszettel zählen als nicht bearbeitet. Bearbeiten Sie die Übungen in Zweiergruppen, und geben Sie sie schriftlich direkt vor der Vorlesung ab, oder werfen Sie sie in den Briefkasten vor dem Sekretariat (Raum 111). Programmieraufgaben müssen zusätzlich über die KVV-Seite hochgeladen werden. In der Regel enthält jeder Zettel drei Aufgaben, die mit Punkten versehen sind.

Kriterien für die erfolgreiche aktive Teilnahme an den Übungen:

Mindestens 60% der erreichbaren Gesamtpunkte der Übungszettel.
Mindestens einmal eine Aufgabenlösung in den Übungen vorstellen.

Übungszettel:

Übungszettel. ohne Abgabe, Besprechung am Mittwoch, 25. 10. 2017, ausgegeben am Dienstag, 17. 4.
Übungszettel. Bearbeitung bis Freitag, 27. 10. 2017, ausgegeben am Freitag, 20. 10.
Übungszettel. Bearbeitung bis Freitag, 10. 11. 2017, ausgegeben am Freitag, 27. 10. Nachtrag zu Aufgabe 19. Weiter unten auf der Seite finden Sie rudimentäre Python-Implementierungen für DCEL, Triangulierung ebener Graphen, und die Berechnung der kanonischen Ordnung.py. Auf diesen Beispielprogrammen können Sie Ihre Überlegegungen zu Aufgabe 19 konkretisieren.
Übungszettel. Bearbeitung bis Freitag, 17. 11. 2017, ausgegeben am Freitag, 10. 11.
Übungszettel. Bearbeitung bis Freitag, 24. 11. 2017, ausgegeben am Freitag, 17. 11.
Übungszettel. Bearbeitung bis Freitag, 1. 12. 2017, ausgegeben am Freitag, 24. 11.
Übungszettel. Bearbeitung bis Freitag, 8. 12. 2017, ausgegeben am Freitag, 1. 12.
Übungszettel. Bearbeitung bis Freitag, 15. 12. 2017, ausgegeben am Freitag, 8. 12.
Übungszettel. Bearbeitung bis Montag, 08. 01. 2018, ausgegeben am Freitag, 15. 12.
Übungszettel. Bearbeitung bis Montag, 08. 01. 2018, ausgegeben am Freitag, 22. 12. Weihnachtsblatt.
Übungszettel. Bearbeitung bis Freitag, 19. 01. 2018, ausgegeben am Freitag, 12. 01.
Übungszettel. Bearbeitung bis Freitag, 26. 01. 2018, ausgegeben am Freitag, 19. 01.
Übungszettel. Bearbeitung bis Freitag, 2. 2. 2018, ausgegeben am Freitag, 26. 1., Aufgabe 53 korrigiert am 30. 1.
Übungszettel. Bearbeitung bis Freitag, 9. 2. 2018, ausgegeben am Freitag, 2. 2.

Inhaltsübersicht

Dienstag, 17. Oktober 2017 (Rote)
- Einführung, Überblick, Motivation
Freitag, 20. Oktober 2017 (Rote)
- Visualisierungspanorama
  - Anwendungen des Graphenzeichnens
  - Kreisförmige U-Bahn-Pläne (von Berlin)
  - Geographisch angepasster U-Bahn-Plan
  - Kartogramme:
    - Entwicklungshilfe
    - Bevölkerung
  - Netzwerke
    - dynamische Visualisierung mit Kräften und Federn
    - Transaktionen bei Bitcoin (zum Vergleich: eine mechanische Visualisierung)
  - Lombardi-Zeichnungen dynamisch. (Über den Künstler Mark Lombardi und seine Zeichnungen.)
- Kräftebasierte Verfahren (erwähnt)
- planare Graphen, ebene Graphen, Einbettungen, Zeichnungen
- Eulerformel, Kuratowski-Kriterium
- Kombinatorische Datenstruktur für ebene Graphen: DCEL
Dienstag, 24. Oktober 2017 (Rote/Klemz)
- Kombinatorische Einbettung von zusammenhängenden Graphen, Kennzeichnung der äußeren Fläche
- Kombinatorische Einbettung (kombinatorische Karte) auf der Kugel und auf anderen orientierbaren Flächen
- Einfügen und Löschen von Kanten in einer DCEL
- Erweiterung um explizite Darstellung von Knoten und Flächen
- Implementierung DCEL.py, für python3
- Geradlinige Zeichnungen
- Ebene Triangulierungen
- Triangulieren von ebenen Graphen
- Implementierung Triangulierung.py
Freitag, 27. Oktober 2017 (Klemz)
- Satz von Wagner-Fáry-Stein
- Kanonische Ordnung für ebene Triangulierungen
- Implementierung CanonicalOrder.py
Freitag, 3. November 2017 (Klemz)
- Verschiebemethode von de Fraysseix, Pach, und Pollack
- Linearzeit-Implementierung von Chrobak und Payne
- Implementierung dFPP.py, und Ausgabe der Zeichnung auf dem Bildschirm
Dienstag, 7. November 2017 (Rote)
- Schnyder-Wälder. Konstruktion und Eigenschaften
- Implementierung Schnyderwood.py
Freitag, 10. November 2017 (Rote)
- Schnyder-Wälder. Kreuzungsfreie Gitterzeichnung
- Jede Triangulierung mit korrekt orientierten Dreiecken ist kreuzungsfrei.
- Die Federmethode von Tutte für geradlinige ebene Zeichnungen in intern 3-zusammenhängenden ebenen Graphen
- Gleichgewichtsbedingung, physikalische Interpretation mit ebenen Kräften
Dienstag, 14. November 2017 (Rote)
- Analyse des Gleichungssystems, diskrete harmonische Funktionen, diskrete Laplace-Matrix Eindeutigkeit der Lösung
- Die Tutte-Einbettung liefert eine ebene Zeichnung (Ausarbeitung)
- Implementierung TutteEmbedding.py
Freitag, 17. November 2017 (Klemz)
- Kontaktrepräsentationen
- Einstieg, Definitionen, Ableiten von Zeichnungen
- Kontaktrepräsentationen mit gleichschenkligen bzw. rechtwinkligen Dreiecken
- Kontaktrepräsentationen mit T-Stücken
- Steigungszahl
- Triviale untere Schranke
- Obere Schranken für die planare 1-Knick-Steigungszahl
Dienstag, 21. November 2017 (Klemz/Rote)
- Untere Schranken für die planare 0-Knick bzw. 1-Knick-Steigungszahl
- Stetige Deformation zwischen Triangulierungen, morphing (erwähnt)
- Exponentielle Gittergröße von Tutte-Einbettungen
- Konstruktion von Polytopen (erwähnt)
Freitag, 24. November 2017 (Rote)
- weitere Kontaktrepräsentationen
- Kreispackungen, Satz von Koebe-Andreyev-Thurston für Triangulierungen, Existenz und Eindeutigkeit
Dienstag, 28. November 2017 (Rote)
- Primal-duale Kreispackungen (erwähnt)
- Planaritätstest
- Reduktion auf dreifach zusammenhängende Graphen
Freitag, 1. Dezember 2017 (Rote)
- Abschnitte und Anschlüsse von Kreisen
- Algorithmus von Auslander und Parter
- s-t-Nummerierung, Ohrenzerlegung, bipolare Orientierungen
- Algorithmus von Lempel, Even, Cederbaum
Dienstag, 5. Dezember 2017 (Rote)
- Tiefensuche
- Zweifacher Zusammenhang
- Algorithmus von Hopcroft und Tarjan
Freitag, 8. Dezember 2017 (Rote)
- PQ-Bäume von Booth und Lueker
- Algorithmus von Lempel, Even, Cederbaum mit PQ-Bäumen
- Varianten von Shih und Xhu und von Boyer und Myrvold
- SPQR-Bäume (erwähnt)
Dienstag, 12. Dezember 2017 (Klemz)
- Orthogonale Zeichnungen
- Algorithmus von Biedl und Kant
- Erweiterung für Graphen mit trennenden Knoten (erwähnt)
- TSM-Framework (Einführung)
Freitag, 15. Dezember 2017 (Klemz)
- Orthogonale Repräsentationen
- Charakterisierung gültiger orthogonaler Repräsentationen
- Zerlegung einer orthogonalen Repräsentation in Rechtecke
Dienstag, 19. Dezember 2017 (Klemz)
- Flussnetzwerke, Min-Cost-Flow Problem
- Zeichnungen gemäß gültiger orthogonaler Repräsentationen erstellen
- Knickminierung per Flussnetzwerkformulierung
- Entsprechung von Flüssen und gültigen orthogonalen Repräsentationen
Dienstag, 9. Januar 2018 (Rote)
- Satz von Hanani-Tutte: Wenn sich je zwei unabhängige Kanten gerade schneiden, ist der Graph planar.
Freitag, 12. Januar 2018 (Klemz)
- Aufwärtsplanarität
- Charakterisierung von aufwärtsplanar Graphen
- geradlinige Aufwärtsplanarität
- Aufwärtsgerichtete, geradlinige Zeichnungen von triangulierten ebenen s-t Graphen
- Exponentialzeit-Test für Aufwärtsplanarität
Dienstag, 16. Januar 2018 (Klemz)
- Charakterisierung aufwärtsplanarer ebener Graphen
- konsistente Großwinkel-Zuweisungen
Freitag, 19. Januar 2018 (Klemz/Rote)
- Test auf Existenz einer konsistenten Großwinkel-Zuweisung
- Test auf Aufwärtsplanarität bei gegebener Einbettung
- Weitere eingeschränkte Varianten aufwärtsplanarer Zeichnungen (erwähnt)
- Planaritätstest mit dem Satz von Hanani-Tutte
- ... durch Lösen eines Gleichungssystems mit O(n²) Variablen und Gleichungen modulo 2.
- Kreuzungszahl
- Planarisierung durch Unterteilung der kreuzenden Kanten
- Kreuzungssatz: cr≥Ω(m³/n²)
Dienstag, 23. Januar 2018 (Klemz)
- Geordnete Level Planarität
- Orthogeodätische Zeichnungen mit festgelegten Koordinaten
- Planares monotones 3SAT
Freitag, 26. Januar 2018 (Rote)
- Ganzzahlige Programmierungsansätze zur Minimierung der Kreuzungszahl
- branch-and-bound, branch-and-cut
Dienstag, 30. Januar 2018 (Rote)
- Maximale planare Untergraphen und Hinzuzeichnen weiterer Kanten
- Grundrisse
- schwach äquivalente Grundrisse
- dual-äquivalente Grundrisse
- Trennende Zerlegungen
Freitag, 2. Februar 2018 (Rote)
- Flächenuniversalität von Grundrissen
Dienstag, 6. Februar 2018 (Klemz)
- 1-Planarität (Survey)
- Planarisierung, 1-ebene Graphen
- Dichte von 1-planarer Graphen
- Dichte von geradlinig 1-planarer Graphen
- Färbbarkeit (erwähnt)
- Nicht-Existenz eines Kuratowski Kriteriums
Freitag, 9. Februar 2018 (Klemz)
- Erkennen von 1-planaren Graphen
- K_6 als unkreuzbarer Teilgraph
- 3-Partition
- Charakterisierung 1-ebener Graphen mit geradliniger Zeichnung (erwähnt)
Dienstag, 13. Februar 2018 (Klemz)
- RAC Zeichnungen (right angle crossing)
- 1-planare 1-Knick RAC Zeichnungen von 1-planaren Graphen
Freitag, 16. Februar 2018 (Rote)
- Planaritätstest von Shih und Xhu

Günter Rote, Impressum