Kurs : SS21: Visualisierung von Graphen

Bölüm anahatları

Genel

Wir beschäftigen uns mit den wichtigsten Algorithmen zum Zeichnen von Graphen. Dabei kommen Methoden aus der Vorlesung Algorithmische Graphentheorie wie Teile und Herrsche, Flussnetzwerke und ganzzahlige Programmierung zum Einsatz. Wir werden Maße für die Qualität einer Graphzeichnung kennenlernen und Algorithmen, die diese Maße optimieren.

Unser Ziel ist es einen Überblick über das Thema Graphvisualisierung zu erlangen und typische Werkzeuge dafür kennen zu lernen. Dadurch wird die Kenntnisse über das Modellieren und Lösen von Problemen mithilfe von Graphen und Graphalgorithmen vertieft.

Vorlesungen:	Videos online vorab, Fragen & Diskussion online Donnerstag 10:15–11:15 Uhr
Übungen:	Montag, 16:00–17:30 Uhr, online
Zoom:	Hier.
Dozenten:	Jonathan Klawitter (Vorlesungen), Myroslav Kryven (Übungen)
Prüfung:	Den Haupttermin für die mündliche Prüfung ist der 19. & 20. Juli. Bei erreichen von mindestens 50% der Punkte auf Übungsblättern gewährt einen Bonus von einem Notenschritt bei Bestehen der Prüfung.
Umgfang:	5 ECTS, 2+2 SWS
Voraussetzung:	Algorithmische Graphentheorie (empfohlen)
Zielgruppe:	Master Informatik, Master Mathematik, Master Computational Mathematics

Anmeldung:

Wenn ihr an der Vorlesung teilnehmen möchtet, meldet euch bitte hier in WueCampus an (oben links auf das blaue Zahnrad klicken und "Mich in diesen Kurs einschreiben" auswählen).

Für die Prüfung ist eine Anmeldung in WueStudy notwendig; der Anmeldungszeitraum ist vom 16. April bis zum 15. Juli.

Chat:

Zur Kommunikation während der Präsenzvorlesung-freien Zeit benutzen wir diesen Channel im Uni Chat. Diesem könnt ihr über diesen Link beitreten. Wir werden diesen Channel für Ankündigungen nutzen und ihr könnt Fragen zu Vorlesungen und Übungen stellen.

Themen und Vorlesungen

Die Vorlesungen stehen euch zur per Videos zur Verfügung. Eine Fragerunde und Diskussion findet online über Zoom statt. Es stehen euch außerdem die Vorlesungvideos vom SS20 noch hier auf WueCampus zur Verfügung.


Termin	Thema & Folien	Videos	Folien lang	Übungsblatt	Literatur
15.04.2021	Einführung Graph Visualisierung Divide & Conquer Methoden: Bäume und series-parallel Graphs	Introduction Layered · HV · Radial · Series-Parallel	Link Link	Link	[GD Ch 3.1 & 3.2]
22.04.2021	Kräfte-basierte Zeichenalgorithmen und Tutte-Einbettungen	Framework · Eades + FR · Variants · Tutte	Link	Link	[DG Ch 4, GD Ch 10]
29.04.2021	Straight-line Zeichnungen planarer Graphen mittels kanonischer Ordnung und Shift-Methode	Intro · Canonical Order · Shift Method	Link	Link	[PGD Ch 4.2, dFPP90]
06.05.2021	Straight-line Zeichnungen planarer Graphen mittels Schnyder Realiser	Baryc. Representation · Schnyder Woods · Drawings	Link	Link	[PGD Ch 4.3, Sch90]
20.05.2021	Orthogonale Zeichnungen mittels Flüssen	Intro · Orthogonal representation · Orthgonal drawing · NP-hardness	Link	Link	[GD Ch 5, PGD Ch 8, Tam87, Pat01]
27.05.2021	Aufwärtsplanare Zeichnungen	Intro · Testing	Link	Link	[GD Ch 6]
10.06.2021	Hierarchische Zeichnungen mit dem Sugiyama Framework	Intro · Step 1 · Step 2 · Step 3 · Step 4 & 5	Link	Link	[GD Ch 11, DG Ch 5]
17.06.2021	Kontaktrepräsentationen	Intro · Triangles · Rectangular Dual	Link	Link	[dFdMR94, He93, KH94]
24.06.2021	Partial Bar Visibility Extension mit SPQR-Bäumen	Intro · Dynamic Program · Reductions	Link	Link	[CGGKL16]
01.07.2021	Kreuzungslemma	Crossing Numbers · Crossing Lemma · Applications	Link	Link	[AZ14, Sze97]
08.07.2021	Beyond Planarity	Intro · Density · Recognition · RAC-Drawings	Link	Link (Bonus)
15.07.2021	Octilineares Graphenzeichnen von Metro Maps	Intro · Path-based, force-based, local · MIP	Link	-	[Nöl14]

Literatur und zusätzliche Materialien bölümünü seçin

Literatur und zusätzliche Materialien
Die Vorlesung basiert hauptsächlich auf Kapiteln aus den folgenden 3 Büchern.

Graph Drawing: Algorithms for the Visualization of Graphs.
Giuseppe Di Battista, Peter Eades, Roberto Tamassia and Ioannis G. Tollis. Prentice Hall, 1999.

Drawing Graphs: Methods and Models.
Michael Kaufmann and Dorothea Wagner (Hrsg.), Lecture Notes in Computer Science, Volume 2025. Springer-Verlag 2001.

Planar Graph Drawing.
Takao Nishizeki and Md Saidur Rahman, Lecture Notes Series on Computing, Volume 12. World Scientific Publishing, 2004.

Weiteres Material werden wir im Verlauf der Vorlesung hier verlinken.

Handbook of Graph Drawing and Visualization.
Roberto Tamassia (Hrsg.), CRC Press, 2013.
- Lecture #1 Supplemental Material: Compendium of Drawing Methods for Trees etkinliğini seçin
  
  Lecture #1 Supplemental Material: Compendium of Drawing Methods for Trees URL
- Lecture #1 [Reingold and Tilford 1981] Tidier Drawings of Trees etkinliğini seçin
  
  Lecture #1 [Reingold and Tilford 1981] Tidier Drawings of Trees URL
- Lecture #1 [Supowit and Reingold 1983] The complexity of drawing trees nicely etkinliğini seçin
  
  Lecture #1 [Supowit and Reingold 1983] The complexity of drawing trees nicely URL
- Lecture #2 Web demo for force-directed approaches etkinliğini seçin
  
  Lecture #2 Web demo for force-directed approaches URL
- Lecture #4 [Schnyder 1990] Embedding Planar Graphs on the Grid etkinliğini seçin
  
  Lecture #4 [Schnyder 1990] Embedding Planar Graphs on the Grid URL
- Lecture #5 [Patrignani 2001] On the complexity of orthogonal compaction etkinliğini seçin
  
  Lecture #5 [Patrignani 2001] On the complexity of orthogonal compaction URL
- Lecture #8 [de Fraysseix, de Mendez, Rosenstiehl 1994] On Triangle Contact Graphs etkinliğini seçin
  
  Lecture #8 [de Fraysseix, de Mendez, Rosenstiehl 1994] On Triangle Contact Graphs URL
- Lecture #8 [He 1993] On Finding the Rectangular Duals of Planar Triangular Graphs etkinliğini seçin
  
  Lecture #8 [He 1993] On Finding the Rectangular Duals of Planar Triangular Graphs URL
- Lecture #8 [Kant and He 1994] Two algorithms for finding rectangular duals of planar graphs etkinliğini seçin
  
  Lecture #8 [Kant and He 1994] Two algorithms for finding rectangular duals of planar graphs URL
- Lecture #9 [CGGKL18] The Partial Visibility Representation Extension Problem etkinliğini seçin
  
  Lecture #9 [CGGKL18] The Partial Visibility Representation Extension Problem URL
- Lecture #10 [Székely 1997] Crossing numbers and hard Erdős problems in discrete geometry etkinliğini seçin
  
  Lecture #10 [Székely 1997] Crossing numbers and hard Erdős problems in discrete geometry URL
- Lecture #10 [Bienstock and Dean 1993] Bounds for rectilinear crossing numbers etkinliğini seçin
  
  Lecture #10 [Bienstock and Dean 1993] Bounds for rectilinear crossing numbers URL
- Lecture #10 [Schaefer 2020] The Graph Crossing Number and its Variants: A Survey etkinliğini seçin
  
  Lecture #10 [Schaefer 2020] The Graph Crossing Number and its Variants: A Survey URL
- Lecture #10 Terry Tao's blog on Crossing Numbers etkinliğini seçin
  
  Lecture #10 Terry Tao's blog on Crossing Numbers URL
- Lecture #10 Movie "N Is a Number: A Portrait of Paul Erdös" etkinliğini seçin
  
  Lecture #10 Movie "N Is a Number: A Portrait of Paul Erdös" URL
- Lecture #12 [Nöl14] A Survey on Automated Metro Map Layout Methods etkinliğini seçin
  
  Lecture #12 [Nöl14] A Survey on Automated Metro Map Layout Methods URL
- Lecture #1-12: Bonus Summary etkinliğini seçin
  
  Lecture #1-12: Bonus Summary Dosya

Tim Hegemann

Jonathan Klawitter

Myroslav Kryven

Alexander Wolff

Bölüm anahatları

Genel

Anmeldung:

Chat:

Themen und Vorlesungen

Literatur und zusätzliche Materialien