Institut für Theoretische Informatik, Algorithmik

Practical Course on Graph Visualisation (Praktikum Graphenvisualisierung)

Summer semester 2015

General Information

  • Class meets: Tuesday 11:30 - 13:00 in Room SR301, (Informatics Building 50.34)
  • Credits: 5
  • Module: Graphenvisualisierung in Theorie und Praxis
  • Language: English
  • Registration: Please register until 10/4/2015 by sending an email to the instructors. Please notice that the number of participants is limited to 14.
  • 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 10/4/2015
  • First lecture on Tuesday 14/4/2015
  • Topic of the project is now known and is described here

Topic

Networks are relational data that increasingly occur in various applications. Network visualisation is a basic tool to explore and understand such networks. There is a plethora of visualization styles, each of which performs better depending on an application the network comes from. The most applied visualisation styles are repeatedly studied in the research areas of Graph Visualization and Graph Drawing. This results in multiple algorithms implementing a particular style. Constructing a visualization of a particular style is usually a multi-criteria optimization problem. These optimization problems are often NP-hard and therefore heuristics are applied for their solution.

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 topic and the procedure of the challenge will be soon announced on the web-page of the symposium. The description of last year's challenge can be found here. 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.

Class Meetings

Date Description Target Slides
Tue, 14.4. Initial meeting Presentation of the structure of the course. Introduction to the topic of the project. Group formation. intro
Tue, 21.4 Literature overview
Tue, 28.4 Literature overview. Distribution of topics.
Tue, 12.5 Presentation of the existing approaches.
Tue, 19.5 Discussion of the software structure.
Tue, 2.6 Questions and progress report.
Tue, 16.6 Questions and progress report.
Tue, 7.7 Questions and progress report.
Tue, 14.7 Final presentations.
Tue, 14.7 Submission of the code 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.

Topic-Specific Literature

[WIKI] Wikipedia page about book embedding Link
[DeKl13] Improved lower bounds on book crossing numbers of complete graphs, by De Klerk et al. SIAM J. DISCRETE MATH., 2013 Link
[Schae14] The Graph Crossing Number and its Variants: A Survey by Marcus Schaefer. Electronic journal of combinatorics, 2014 Link
[Nich68] Permutation procedure for minimizing the number of crossings in a network, by T. A. J. Nicholson. Proceedings of the Institution of Electrical Engineers, 1968 Link
[He05] Crossing Minimisation Heuristics for 2-page Drawings, by H. He et al. Electronic Notes in Discrete Mathematics, 2005 Link
[Cimi05] Algorithms for the fixed linear crossing number problem, by Robert Cimikowski. Discrete Applied Mathematics 2002 Link
[Cimi07] Approximating the fixed linear crossing number, by Robert Cimikowski, Brendan Mumey. Discrete Applied Mathematics 2007 Link
[Sats13] K -page crossing number minimization problem: An evaluation of heuristics and its solution using GESAKP, by Satsangi et al. Memetic Computing 2013
[Sats12] PAGE NUMBER PROBLEM: AN EVALUATION OF HEURISTICS AND ITS SOLUTION USING A HYBRID EVOLUTIONARY ALGORITHM, by Satsangi et al., International Journal of Computer Science 2012 Link
[Lopez07] K-Pages Graph Drawing with Multivalued Neural Networks, by López-Rodríguez et al. Artificial Neural Networks 2007 Link
[Shah07] Book embeddings and crossing numbers, by Shahrokhi et al., Graph-Theoretic Concepts in Computer Science 1995 Link
[Bern79] The book thickness of a graph, by Bernhart and Kainen, Journal of Combinatorial Theory, Series B, 1979 Link
[Thesis2007] Master thesis: Analysis of algorithms for computing the crossing number (see chapter 10), by Helena Kocurova, 2007 Link
[Banzal2008] An evolutionary algorithm for the 2-page crossing number problem, by Bansal et al., Evolutionary Computation, 2008. Link
[Buchheim2006] Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem, by Buchheim and Zheng, Computing and Combinatorics, LNCS, 2006. Link
[Chung87] EMBEDDING GRAPHS IN BOOKS: A LAYOUT PROBLEM WITH APPLICATIONS TO VLSI DESIGN, by CHUNG et al., SIAM journal of Disc. Meth., 1987 Link
[Bilski92] Embedding graphs in books: a survey, by Bilski, Computers and Digital Techniques, 1992 Link
[Poranen06] A Simulated Annealing Algorithm for the 2-page Crossing Number Problem, by Poranen et al., Proceedings of Graph Drawing, 2006 Link
[BaurBrandes04] Crossing Reduction in Circular Layouts, by Baur and Brandes, Proceedings of WG, 2004 Link
[He07] Genetic algorithms for the 2-page book drawing problem of graphs, by He et al., Journal of Heuristics, 2007 Link

Categorization of Literature

Paper-ID 2-page planar 2-page crossing-min k-page planar k-page crossing min fixed order flexible order
[Sats12], [Sats13] X X
[Banzal08] X Ext X
[Lopez07] X X
[Thesis07] X X X
[He07] X Ext X
[Buchheim06] X Ext X
[Poranen06] X X
[He05] X X X
[Cimi05], [Cimi07] X Ext? X
[Shah95] X X
[Bilski92], [Chung87] X X X
[Bern79] X X
[Nich68] X X