Abschnittsübersicht

• Abschnitt Allgemeines auswählen

  Allgemeines

  Alles einklappen Alles aufklappen

  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.

  
  
• Abschnitt Themen und Vorlesungen auswählen

  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]
• Abschnitt Literatur und zusätzliche Materialien auswählen

  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.
    

  • Aktivität Lecture #1 Supplemental Material: Compendium of Drawing Methods for Trees auswählen

    

    Lecture #1 Supplemental Material: Compendium of Drawing Methods for Trees Link/URL
  • Aktivität Lecture #1 [Reingold and Tilford 1981] Tidier Drawings of Trees auswählen

    

    Lecture #1 [Reingold and Tilford 1981] Tidier Drawings of Trees Link/URL
  • Aktivität Lecture #1 [Supowit and Reingold 1983] The complexity of drawing trees nicely auswählen

    

    Lecture #1 [Supowit and Reingold 1983] The complexity of drawing trees nicely Link/URL
  • Aktivität Lecture #2 Web demo for force-directed approaches auswählen

    

    Lecture #2 Web demo for force-directed approaches Link/URL
  • Aktivität Lecture #4 [Schnyder 1990] Embedding Planar Graphs on the Grid auswählen

    

    Lecture #4 [Schnyder 1990] Embedding Planar Graphs on the Grid Link/URL
  • Aktivität Lecture #5 [Patrignani 2001] On the complexity of orthogonal compaction auswählen

    

    Lecture #5 [Patrignani 2001] On the complexity of orthogonal compaction Link/URL
  • Aktivität Lecture #8 [de Fraysseix, de Mendez, Rosenstiehl 1994] On Triangle Contact Graphs auswählen

    

    Lecture #8 [de Fraysseix, de Mendez, Rosenstiehl 1994] On Triangle Contact Graphs Link/URL
  • Aktivität Lecture #8 [He 1993] On Finding the Rectangular Duals of Planar Triangular Graphs auswählen

    

    Lecture #8 [He 1993] On Finding the Rectangular Duals of Planar Triangular Graphs Link/URL
  • Aktivität Lecture #8 [Kant and He 1994] Two algorithms for finding rectangular duals of planar graphs auswählen

    

    Lecture #8 [Kant and He 1994] Two algorithms for finding rectangular duals of planar graphs Link/URL
  • Aktivität Lecture #9 [CGGKL18] The Partial Visibility Representation Extension Problem auswählen

    

    Lecture #9 [CGGKL18] The Partial Visibility Representation Extension Problem Link/URL
  • Aktivität Lecture #10 [Székely 1997] Crossing numbers and hard Erdős problems in discrete geometry auswählen

    

    Lecture #10 [Székely 1997] Crossing numbers and hard Erdős problems in discrete geometry Link/URL
  • Aktivität Lecture #10 [Bienstock and Dean 1993] Bounds for rectilinear crossing numbers auswählen

    

    Lecture #10 [Bienstock and Dean 1993] Bounds for rectilinear crossing numbers Link/URL
  • Aktivität Lecture #10 [Schaefer 2020] The Graph Crossing Number and its Variants: A Survey auswählen

    

    Lecture #10 [Schaefer 2020] The Graph Crossing Number and its Variants: A Survey Link/URL
  • Aktivität Lecture #10 Terry Tao's blog on Crossing Numbers auswählen

    

    Lecture #10 Terry Tao's blog on Crossing Numbers Link/URL
  • Aktivität Lecture #10 Movie "N Is a Number: A Portrait of Paul Erdös" auswählen

    

    Lecture #10 Movie "N Is a Number: A Portrait of Paul Erdös" Link/URL
  • Aktivität Lecture #12 [Nöl14] A Survey on Automated Metro Map Layout Methods auswählen

    

    Lecture #12 [Nöl14] A Survey on Automated Metro Map Layout Methods Link/URL
  • Aktivität Lecture #1-12: Bonus Summary auswählen

    

    Lecture #1-12: Bonus Summary Datei