Automatisches Zeichnen von Graphen (Winter 2018/19, Uni zu Köln)

Diese Vorlesung behandelt ausgewählte Bereiche des automatischen Graphenzeichnens.

Vorlesung: Montags 14:00-15:30 und Donnerstags 10:00-11:30, Hörsaal Alte Botanik 136/01 in der Gyrhofstr. 15 1. OG
Dozent: Jens M. Schmidt
Übung:
Startet 5-zügig ab dem 23.10.2018 mit dieser Übungszuteilung. Eine Gruppenbearbeitung der Übungsabgaben mit bis zu 3 Personen ist erlaubt. Pro Gruppe ist nur eine Ausarbeitung einzureichen, die entweder handschriftlich oder maschinengeschrieben sein muss. Kopien handschriftlicher Abgaben werden generell nicht gewertet. Die Ausarbeitungen sind immer bis zum Mittwoch 12:00 Uhr der Woche vor der Besprechung des jeweiligen Übungsblattes im Fach des Institutes für Informatik, Weyertal 121, einzuwerfen (die erste Ausarbeitung also am 17.10.2019). Das Fach finden Sie auf der 5. Etage im Eingangsbereich zur Bibliothek. Bitte beachten Sie: Die Tür zum Eingangsbereich der Bibliothek ist von Montags bis Freitags zwischen 10 und 20 Uhr geöffnet.
Forum: Ein Forum rund um die Vorlesung und Übung ist in ILIAS verfügbar.
Tutor: Alexander ApkeArne Heimendahl, David Könen, Robin Kühling und Jens M. Schmidt
SWS: 4V+2Ü
Zielgruppe: Mathematik Master, Wirtschaftsinformatik Bachelor
Voraussetzungen: Kenntnisse in Effizienter Algorithmik und Graphen
Prüfung:
Zum Ende des Semesters wird eine schriftliche Klausur am 11.02.2019 (11:00-14:00 Uhr im Hörsaal Ch I + II) und Nachklausur am 12.03.2019 (13:00-16:00 Uhr im Hörsaal Ch I) angeboten. Für die Zulassung zu den Klausuren ist es notwendig, mindestens 50% der Gesamtpunkte aller Übungsaufgaben zu erreichen, und falls vom Übungsleiter gewünscht, deren Lösungen fehlerfrei und sicher vorzutragen. Lösungen zu den Programmieraufgaben innerhalb der OGDF müssen dem Übungsgruppenleiter vor der Übung per Email mit Source-Code, ausführbarer Datei und (falls vorhanden) Ausgabe zugesendet werden.
Klausureinsicht: 20.03.2019 10:00 Uhr im Seminarraum im Weyertal 80.
Literatur:
  • Di Battista, Eades, Tamassia, Tollis - Graph Drawing: Algorithms for the visualization of graphs, Prentice Hall, 1999.
  • Nishizeki, Rahman - Planar Graph Drawing, Lecture Notes Series on Computing 12, Springer, 2004.
  • Tamassia - Handbook of Graph Drawing and Visualization, CRC Press, 2016.
  • Jünger, Mutzel - Graph Drawing Software, Mathematics and Visualization, Springer, 2004.
  • Kaufmann, Wagner - Drawing Graphs: Methods and Models, Lecture Notes in Computer Science 2025, Springer, 2001.



Nr. Inhalt Slides (Druckv., einige geschüzt) Übung
01. Grundlagen Einführung, Überblick und Motivation, Layout-Problem Slides
02. Grundlagen Zeichenkonventionen, Optimierungskriterien für gute Zeichnungen, Konfliktkriterien, Anwendungs-Wunschkonzert Slides ueb01.pdf
Uebung01.cpp
03. Grundlagen Unit-cost RAM, Worst-Case Laufzeit, Zeitkomplexität, Halbkanten-Datenstruktur für Graphen, Repräsentation eingebetteter Graphen, Topologische Sortierung

04. Baumzeichnungen Zeichenkonventionen, Baumtraversierungen, Inorder-Algorithmus, Algorithmus von Reingold-Tilford, Konturen, Laufzeit O(n), Kritikpunkt Breite Slides ueb02.pdf
05. Baumzeichnungen Zeichnungen minimaler Breite, LP-Formulierung, Kodierung isomorpher Unterbäume, Laufzeit, Gitterzeichnungen minimaler Breite Slides
06. Baumzeichnungen Zeichnen von allgemeinen Bäumen, Radiale Baumzeichnungen in Zeit O(n) Slides ueb03.pdf
Uebung03.cpp
07. Zeichnungen Serien- Paralleler Graphen Serien-Parallele Graphen, Dekompositionsbäume und Rechtslastigkeit, Kriterien, Zeichenalgorithmus von Bertolazzi et al. in Zeit O(n)
Slides
08. Allerheiligen ueb04.pdf
09. Zeichnungen Serien- Paralleler Graphen Invarianten des Zeichenalgorithmus, Abschätzung der Fläche, Einbettungserhaltende Zeichnungen Slides
10. Zeichnungen Serien- Paralleler Graphen Symmetriegruppen von Punktmengen und Zeichnungen, gerichtete Automorphismen, Darstellbarkeit von Automorphismengruppen, Charakterisierung in serien-parallelen Graphen, Algorithmus von Hong-Eades-Lee Slides ueb05.pdf
11. Hierarchisches Graphenzeichnen Sugiyama-Methode, Kreisentfernung: Berger-Shor in Zeit O(n+m), Eades-Lin-Smyth mit Güte m/2+n/6 Slides
12. Hierarchisches Graphenzeichnen Schichtzuweisung: Höhenminimierungsalgorithmus in Zeit O(n+m), Coffman-Graham, Kompakte Schichtungen, Minimierung der Anzahl von Dummy Vertices Slides ueb06.pdf
Uebung06.cpp
example.gml
13. Hierarchisches Graphenzeichnen Kreuzungsminimierung: Schicht-für-Schicht Traversierung, NP-Vollständigkeit fixierte bipartite Kreuzungszahl, Inversionen, Kreuzungszählen in Laufzeiten O(m2), O(m+#Kreuzungen), O(m log min{|A|,|B|}) und O(m log n / log log m), Experimentelle Laufzeiten Slides
14.
Feedback-Besprechung Fachschaft Wirtschaftsinformatik ueb07.pdf
15. Hierarchisches Graphenzeichnen Heuristik für untere Schranke und für obere Schranken: Greedy-Insert, Greedy-Switch, Split, Barycenter, Median, Pathologische Beispiele, 3-Approximation mit Median, Experimentelle Laufzeiten Slides
16. Hierarchisches Graphenzeichnen Exakte und heuristische horizontale Koordinatenzuweisung, Kantenzeichnen, Definition k-kanten- und k-zusammenhängende Graphen Slides ueb08.pdf
Uebung08.cpp
17. Zusammenhangs- Voraussetzungen 2-Zusammenhang mit Chain Decompositions: Ohrendekompositionen, 2-Kanten- und 2-Zusammenhangstests, starke Orientierungen in jeweils Zeit O(m), Definition st-Orientierungen und -numberings Slides
18. Zusammenhangs- Voraussetzungen Badent 2002, Easy st-Numberings 2019, und Block-Cut-Trees in jeweils Zeit O(m)
2-kontrahierbare Kanten nicht behandelt
Slides ueb09.pdf
19. Zusammenhangs- Voraussetzungen 3-Zusammenhang, Tutte Splits, 3-Zusammenhangskomponenten
Slides
20. Planare Graphen Grundlagen planarer Graphen, Eulerformel, Stereographische Projektion, Maximal Planare Graphen, Nicht-Planarität von K3,3 und K5
ueb10.pdf
21. Planare Graphen Sätze von Kuratowski und Wagner, Platonische Körper, Planare Dualität
22. Planare Graphen SPQR-Bäume + Berechnungsidee, Anzahl kombinatorischer Einbettungen planarer Graphen Slides ueb11.pdf
Uebung11.cpp
christmastree.gml
23. Planare Graphen Ausflug auf orientierbare Oberflächen, Geschlecht, Klassifikationstheorem (ohne Beweis), Zelluläre Zeichnungen, Rotationssysteme, Kombinatorische Flächen, Geschlecht bei gegebenem Rotationssystem
Slides
24. Planare Graphen Planaritätstest von Boyer-Myrvold in Zeit O(n): Walkup, Walkdown, Korrektheit Slides ueb12.pdf
25. Planare Graphen Planaritätstest von Boyer-Myrvold in Zeit O(n): Kuratowski-Minorenextraktion, Laufzeit, Beweis von Kuratowskis und Wagners Theorem Slides
26. Geradlinige Zeichnungen Geradlinige Zeichnungen, Kanonische Ordnungen, Shift-Algorithmus, Mondshein-Sequenz Slides
ueb13.pdf
27. Geradlinige Zeichnungen Berechnung der Mondshein-Sequenz: BG-Operationen, Bijektion zu BG-Pfaden und Existenz, Berechnung BG-Sequenz in Zeit O(n2), Induktion über BG-Sequenz Slides
28. Geradlinige Zeichnungen Anwendungen der Mondshein-Sequenz: Alternativer Planaritätstest, Unabhängige Spannbäume, 3-Partitionsproblem Slides Besprechung
29. Geradlinige Zeichnungen Planare st-Orientierungen, Barnettes Theorem (nicht behandelt) Slides
30. Kräftebasiertes Zeichnen Physikalisches Modell, Kräfte, Spring Embedder, Tuttes Schwerpunkt-Methode, Geometrische Interpretation, Varianten Slides