Institut für Theoretische Informatik, Algorithmik

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

Summer semester 2017

General Information

  • Class meets: Thursday 14:00 h, R-108, (Informatics Building 50.34)
  • Credits: 5
  • Module: Praktikum: Graphenvisualisierung in der Praxis [M-INFO-103302, Examination no. 2400037]
  • Language: English
  • Registration: Please register until 21/4/2017 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“.

News

  • Registration open until 21/4/2017
  • First lecture on Thursday 27/4/2017

Topic

In this practical course we study the problem of maximizing the angular resolution in straight-line drawings of a graph, e.g. the smallest angle between any pair of crossing edges in a straight-line drawing. Determining whether a biconnected planar graph has an angular resolution greater then a constant is already NP-Hard. Thus, the aim of this course is to develop efficient heuristics to optimize the angular resolution of arbitrary graphs.

There are further details on the Graph Drawing Challenge Website.

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

Online Graph Drawing Challenge

The teams with the best programs are encouraged and will be provided any necessary help to participate in the Graph Drawing Challenge held annually during the International Symposium on Graph Drawing & Network Visualization. The winners of the 2014 challenge in the automatic category are Alexander Khomenko, Igor Karlinsky, and Denis Knöpfle from KIT who implemented their software during the Graph Visualisation course 2013-2014.

Meetings

Date Time Where Topic
27.05 14:00 -108 Organization and Introduction to the topic
Search, read and understand related work
15.05 16:00 315 Discussion of the found work, Brainstorming
18.05 14:00 315 Discussion of the found work, Brainstorming
Search, read and understand related work
24.05 14:30 315 Discussion, Brainstorming, Distribution
Development
01.06 14:00 315 Questions, Brainstorming, Test instances
Development, testing
08.06 14:00 315 Questions, Brainstorming
Development, testing
22.06 14:00 315 Questions, Brainstorming
Development, testing
06.07 14:00 315 Final Implementation Ideas
Development, testing (till July 10th), Presentation preparation
20.07 14:00 315 Final Presentations
Documentation
27.07 14:00 315 Submit the software and the documentation

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.