Topic outline

  • General

    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
    Dozenten: Jonathan Klawitter (Vorlesungen), Myroslav Kryven (Übungen)
    Prüfung: Den Haupttermin für die Prüfung werden wir während des Semesters bekannt geben.
    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.

    rocket.chat logoChat:
    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 · Radial · HV · Series-Parallel
      		Link
      Link
      		Link
      		[GD Ch 3.1 & 3.2]
      22.04.2021
      		Kräfte-basierte Zeichenalgorithmen und Tutte-Einbettungen



      29.04.2021 Straight-line Zeichnungen planarer Graphen
      mittels kanonischer Ordnung und Shift-Methode




      06.05.2021 Straight-line Zeichnungen planarer Graphen mittels Schnyder Realiser




      20.05.2021
      		Orthogonale Zeichnungen mittels Flüssen




      27.05.2021 Octilineares Graphenzeichnen von Metro Maps



      10.06.2021 Aufwärtsplanare Zeichnungen




      17.06.2021 Hierarchische Zeichnungen mit dem Sugiyama Framework




      24.06.2021 Kontaktrepräsentationen




      01.07.2021 Partial Bar Visibility Extension mit SPQR-Bäumen



      08.07.2021 Kreuzungslemma


      15.07.2021 Beyond Planarity




      • Übungen und Übungsblätter

        Wie auch die Vorlesungen wird die Übung via Zoom stattfinden; für manche Übungsaufgaben werden Videos mit der Lösung hochgeladen.

        Jede Woch werden wir zum Vorlesungstermin ein neues Übungsblatt hochladen (zur letzten Vorlesung wird es kein Übungsblatt geben). Abgabetermin ist der darauffolgende Vorlesungstermin. Auf jedem Übungsblatt kann man 20 Punkte erreichen. Das Erlangen von insgesamt mindestens 50% der Punkte gewährt einen Bonus von einem Notenschritt bei Bestehen der Prüfung. Zur letzten Vorlesung wird es kein Übungsblatt geben.

        Übungsblätter dürfen zu zweit bearbeitet werden und werden dann in digital Form abgegeben. Sie sollten daher wenn möglich am Computer geschrieben werden. Wir empfehlen die Verwendung von LaTeX und gerne die hierfür bereitgestellte Vorlage. Die Übungsblätter können in Deutsch oder Englisch verfasst werden.

      • 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.