Practical Course: Graph Visualisation in Practice (Praktikum Graphenvisualisierung in der Praxis)

Summer semester 2019

General Information

  • Class meets:: to be announced
  • Credits: 5
  • Module: Praktikum: Graphenvisualisierung in der Praxis [M-INFO-103302, Examination no. 2400037]
  • Language: English
  • Registration: Please register until 17/4/2019 by sending an email to both instructors. Please notice that the number of participants is limited to 9.
  • Grading scheme: The final grade depends on: the successful completion of the project (70%), final presentation (20%) and the written documentation (10%).
  • Prerequisites: The course is open only for the students who passed the course „Algorithms for Graph Visualization“ or „Computational Geometry“.

News

  • 22.03.2019 - Topics are online

Topics

  • Solving Hard Geometric Optimization Problem

Given a set S of n points in the plane, compute a simple polygon whose vertex set is precisely the set S (called polygonization of S), that has maximum or minimum area among all polygonalizations of S. Our goal is to design a heuristic algorithm, implement it and evaluate its performance.

This problem is currently the topic of optimization challenge organized during CG Week 2019.

  • Visualization of the Faust Editions Network

In a complex digital edition of Goethe’s Faust the chronological relations (edges) between manuscripts (nodes) represent a directed network with several thousands of nodes. Literary scholars gain new insight when investigating this network. Our main goal is come up with abstraction techniques that would allow researchers to understand better the structure of the network. We will implement and evaluate these techniques with the real data set.

This project is a collaboration with Professor of Digital Humanities, Fotis Jannidis (University of Würzburg). Check also the web-page of the FAUSTEDITION project.

  • Visualization of Hypergraphs Using Metro Map Metaphor

A hypergraph is a collection of elements (vertices) and their subsets (hyperedges). Visualization of hypergraphs is a highly complex task and the known to date techniques, for instance Venn diagrams, do not scale well. Our goal is to develop algorithms that visualize hypergraphs as metro maps: each vertex is represented as a station and each hyperedge as a metro-line. We will implement and evaluate the designed algorithm.

Structure

In this course, participants will work in small groups on a selected optimisation problem in the area of graph visualization from a practical perspective. The aim is to produce, by the end of the course, an executable program which creates a particular layout style and solves the optimisation problem as well as possible. Specifically, the three main phases of the course are:

  • Mastering the relevant existing literature on the subject
  • Design of own solutions, based on adaptations and combinations of existing algorithms, as well as development of new heuristics
  • Implementation and evaluation of the developed solutions

General Reading on Graph Drawing

[BETT99] G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.
[KW01] M. Kaufmann, D. Wagner: Drawing Graphs: Methods and Models, Springer-Verlag, 2001
[NR04] T. Nishizeki, Md. S. Rahman: Planar Graph Drawing, World Scientific, 2004
[T13] R. Tamassia: Handbook of Graph Drawing and Visualization, CRC Press, 2013.