Veranstaltung

Graphen sind mathematische Modelle von Netzwerken, die in einer Vielzahl von Anwendungen Verwendung finden. Die Graphenvisualisierung ist ein grundlegendes Werkzeug für menschliche Betrachter, um solche Graphen zu untersuchen und zu verstehen. Es gibt eine große Zahl verschiedener Visualisierungsstile, die je nach Anwendung unterschiedlich sinnvoll sind. Für die am häufigsten verwendeten Stile existieren dementsprechen vielfältige Layoutalgorithmen im Forschungsbereich des Graphenzeichnens. Im Kern vieler Graphenlayoutprobleme zu einem gewissen Zeichenstil liegen (multikriterielle) Optimierungsprobleme. Oft sind diese Optimierungsprobleme NP-schwer und werden daher heuristisch gelöst.

In diesem Kurs bearbeiten die Teilnehmer in Kleingruppen ein ausgewähltes Optimierungsproblem im Bereich der Graphenvisualisierung aus praktischer Sicht. Ziel ist es, bis zum Ende des Praktikums ein lauffähiges Programm zum Zeichnen von Graphen im vorgegebenen Layoutstil zu erstellen, das das Optimierungsproblem möglichst gut löst. Die Teams mit den besten Programmen können im Anschluss am alljährlichen internationalen Graph Drawing Contest teilnehmen.

Im Einzelnen besteht das Praktikum aus drei Phasen:

1.) Erarbeiten der relevanten bestehenden Literatur zum Thema

2.) Entwurf eigener Lösungsansätze, beruhend auf Anpassungen und Kombinationen der bestehenden Algorithmen, sowie durch Entwicklung neuer heuristischer Verfahren

3.) Implementierung und Evaluation der entwickelten Lösungsansätze

Lernziele: 
Nach erfolgreichem Besuch des Praktikums sollen die Studierenden

• sich eigenständig in Fachliteratur einarbeiten können;
• im Team basierend auf den Techniken aus der Literatur neue Lösungsideen für die aktuelle Fragestellung des Graph Drawing Contests entwickeln, diskutieren und bewerten können;
• im Team die eigenen Lösungsideen implementieren und ein Programm für die Wettbewerbsteilnahme entwickeln können;
• die Arbeitsergebnisse in einem wissenschaftlichen Vortrag präsentieren können.

Voraussetzungen:
Die Lehrveranstaltung "Algorithmen zur Visualisierung von Graphen" im selben Modul muss bestanden sein, bevor das Praktikum "Graphenvisualisierung" geprüft werden kann.

Empfehlungen: Programmierkenntnisse werden vorausgesetzt.

Arbeitsaufwand: 150h

Die Erfolgskontrolle wird in der Modulbeschreibung erläutert.