Schema della sezione

  • Introduzione

    Minimizza tutto Espandi tutto

  • Seminar: Visualisierung von Graphen

    Umfang:

    5 ECTS, 2 SWS

    Zeit & Ort:

    dienstags, 14:15–15:45 Uhr, SE III

    Voraussetzung:  

    Algorithmische Graphentheorie (empfohlen)

    Zielgruppe:

    Master Informatik (empfohlen), Bachelor Informatik

    Dozenten:

    Steven Chaplick, Philipp Kindermann und Alexander Wolff


    Der erste Termin ist am Di, 15.10.2019. An diesem Termin bitten wir um vollständige Anwesenheit, da wir den Ablauf des Seminars besprechen und die folgenden Vortragsthemen vorstellen und verteilen.

    Author Artikel Betreuer Vortragende
    Nickel et al. 
    		Computing Stable Demers Cartograms
         		Philipp Kindermann Dimitri
    Bhore et al.
    		Parameterized Algorithms for Book Embedding Problems
    		Philipp Kindermann
    		 Ludwig
    Merker et al.
    		Local and Union Page Numbers
    		Jonathan Klawitter Fabian
    Brückner et al.
    		Level-Planar Drawings with Few Slopes Philipp Kindermann Rebecca & Florian
    Van Goethem et al.
    		Optimal Morphs of Planar Orthogonal Drawings II
    		Steven Chaplick Bastian
    Hliněný et al.
    		Exact Crossing Number Parameterized by Vertex Cover
         		Steven Chaplick
    		 Annika
    Biedl et al.
    		Homotopy Height, Grid-Major Height and Graph-Drawing Height
    		Steven Chaplick
    		 Max
    Borrazzo et al.
    		On the Edge-Length Ratio of Planar Graphs
    oder On the Edge-length Ratio of Outerplanar Graphs (GD 2017)     		Alexander Wolff Moritz
    Angori et al.
    		ChordLink: A New Hybrid Visualization Model
         		Johannes Zink Jan & Felix
    Felsner
    		4-Connected Triangulations on Few Lines
    		Alexander Wolff
    		 Leon

    Bitte schreiben Sie sich schon vorher in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen wollen.

    • Thema

      Wir beschäftigen uns mit Algorithmen zum Zeichnen von Graphen. Dabei kommen Methoden aus der Vorlesung Algorithmische Graphentheorie wie beispielsweise Teile und Herrsche, Flussnetzwerke, ganzzahlige Programmierung und das Planar-Separator-Theorem zum Einsatz. 


      Lernziele

      Die TeilnehmerInnen lernen, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen KursteilnehmerInnen in einem Vortrag zu vermitteln.

      Sie bekommen im Seminar einen Überblick über Techniken der Graphvisualisierung und vertiefen ihre Kenntnisse über das Modellieren und Lösen von Problemen mithilfe von Graphen und Graphalgorithmen. Dieses Thema eignet sich übrigens auch gut für Abschlussarbeiten.

      Außerdem sollen sie einen Eindruck von Forschung in der Informatik bekommen: vom Erkennen und Formulieren geeigneter Problemstellungen über das Entwickeln von Lösungsstrategien für diese Probleme bis zum Festhalten der Ergebnisse in einer wissenschaftlichen Arbeit.

      Module

      Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik eingetragen. Bei großem Engagement über den Vortrag und die Ausarbeitung hinaus (siehe Ablauf), wäre auch eine Anrechnung als Praktikum denkbar.

      Allgemeine Literatur zum Graphzeichnen

      • Graph Drawing: Algorithms for the Visualization of Graphs
        Giuseppe Di Battista, Peter Eades, Roberto Tamassia und Ioannis G. Tollis. Prentice Hall,1998. 
      • The Handbook of Graph Drawing and Visualization
        Roberto Tamassia (Hrsg.). CRC Press, 2014.
      • Drawing Graphs: Methods and Models
        Michael Kaufmann und Dorothea Wagner (Hrsg.), Lecture Notes in Computer Science, Band 2025. Springer-Verlag, 2001.
      • Planar Graph Drawing
        Takao Nishizeki und Md Saidur Rahman, Lecture Notes Series on Computing, Band 12. World Scientific Publishing, 2004.

  • Termine

    Termin Thema Vortragende(r) Betreuer
    15.10.2019 Einführung, Themenvergabe Alle
    22.10.2019 Kurzvorträge Alle
    05.11.2019  ChordLink: A New Hybrid Visualization Model
    		 Jan Sauer & Felix Heinickel Johannes Zink
    12.11.2019
    		 On the Edge-length Ratio of (Outer-)Planar Graphs
    		 Moritz Niederer Alexander Wolff
    19.11.2019
    		 Level-Planar Drawings with Few Slopes
    		 Rebecca Kraus & Florian Mittelstädt Philipp Kindermann
    26.11.2019
    		 Exact Crossing Number Parameterized by Vertex Cover
    		 Annika Förster Steven Chaplick

    		4-Connected Triangulations on Few Lines
    		 Leon Füger Alexander Wolff
    03.12.2019
    		 Computing Stable Demers Cartograms
    		 Dimitri Klippert Philipp Kindermann
      Optimal Morphs of Planar Orthogonal Drawings II
    		 Bastian Häuser Steven Chaplick
    17.12.2019 Parameterized Algorithms for Book Embedding Problems
    		 Ludwig Scheuring Philipp Kindermann
      Local and Union Page Numbers
    		 Fabian Egidy Jonathan Klawitter
    15.01.2020 Abgabe Ausarbeitung Alle
    Condizioni per l'accesso: Appartenere al gruppo Seminarteilnehmer

  • Ablauf

    1. Im ersten Treffen werden wir einen kurzen Überblick über die möglichen Themen geben und diese auf die Teilnehmer verteilen. Davor werden wir den Ablauf des Seminars erklären
    2. Im zweiten Treffen gibt jeder Teilnehmer einen kurzen Überblick über sein Thema (max. 5 Minuten, 3 Folien). Außerdem werden wir Genaueres zur Gestaltung der Vorträge und der Ausarbeitung sagen.
    3. In den folgenden Treffen finden die eigentlichen Vorträge der Teilnehmer statt. Neben dem Vortrag bleibt auch Zeit zur Diskussion der Themen und daraus resultierender offener Fragen für die weitere Forschung.
    4. Die verbleibenden Treffen bis zum Semesterende wollen wir zur weiteren Arbeit an diesen offenen Fragen nutzen. Je nach Erfolg könnte daraus ein gemeinsamer Artikel werden (beispielsweise auf der GD 2019).

  • Themen

    Grundlage jedes Vortragsthemas sind ein oder mehrere wissenschaftliche Artikel. Die Themen basieren meist auf aktuellen Forschungsergebnissen, die beispielsweise auf dem 27th International Symposium on Graph Drawing & Network Visualization (GD 2018) vorgestellt wurden.

    Für jedes Thema geben wir einen Artikel bzw. ein Buchkapitel vor. Sie sollen aber auch noch selbst Literaturrecherche betreiben. Ein Ausgangspunkt dafür können beispielsweise die Referenzen in ihrem Artikel sein. Da wir das Seminar auf die aktuelle Forschung hin ausrichten wollen, sind insbesondere offene Fragen ein wichtiger Bestandteil der Themen.

  • Vorträge

    • Ihr Vortrag sollte etwa 30 Minuten (bei Einzelvorträgen) bzw. 45 Minuten (zu zweit) dauern.
    • Wir empfehlen für die Erstellung der Folien das kostenlose Programm ipe (verfügbar für Linux, Windows, Mac). Als Einstieg können Sie gerne einen Blick auf die Folien vom Einführungsvortrag werfen. Die PDF-Datei können Sie mit ipe öffnen und weiterbearbeiten.
    • Auch im Vortrag sollten offene Probleme nicht zu kurz kommen.
    • Die Folien ihres Vortrages werden wir anschließend hier für alle Teilnehmer zur Verfügung stellen.

  • Ausarbeitungen

    Die Ausarbeitung zu ihrem Thema sollte etwa 10 Seiten (zuzüglich Titelseite) umfassen. Sie soll nicht nur den von uns vorgegebenen Artikel zusammenfassen, sondern auch darüber hinaus gehen. Zum Einen eignet sich dafür das Material, dass sie durch eigene Literaturrecherche gefunden haben. Zum anderen kann man auch hier wieder die Forschungskomponente des Seminars deutlich machen: entwickeln Sie eigene neue Fragestellungen! Nehmen Sie auch Anregungen in ihre Ausarbeitung mit auf, die in der Diskussion nach Ihrem Vortrag geäußert werden.

    Die Themen des Seminars sollen nicht für sich alleine stehen, sondern wurden bewusst aus einem bestimmten Gebiet gewählt. Nutzen Sie das in ihrer Ausarbeitung und zeigen Sie Verbindungen zu anderen Vortragsthemen des Seminars auf! Vielleicht können Sie dadurch auch neue Fragestellungen entwickeln, die für die weitere Forschung interessant sind. Damit Sie die Möglichkeit haben Ergebnisse aus den anderen Vorträgen in Ihre Ausarbeitung aufzunehmen, muss diese erst eine Woche nach dem letzten Vortrag abgegeben werden.

    Die Ausarbeitungen sollen mit LaTeX erstellt werden. Wenn Sie noch keine Erfahrung mit LaTeX haben, könnte dieser kostenlose Kurs im Rechenzentrum hilfreich sein.

  • Bewertung

    Voraussetzungen für das Bestehen des Seminars:

    • Halten einer Präsentation zum gewählten Thema
    • Anfertigen einer Ausarbeitung
    • Regelmäßige Teilnahme am Seminar und aktive Mitarbeit (einmaliges Fehlen bei einem Vortrag ist erlaubt)