Graph Drawing (DA4124)

Professor

Prof. Dr. Andreas Kerren

Time & Place

Compare here (DA4124)

Teaching Period

II (2009-11-04 till 2010-01-13)

Assessment

Assignments and oral examinations. Oral examinations will take place in week 4, between 25/1 and 29/1.

Prerequisites

At least two years of university studies (equal to 120 Swedish credit points), including knowledge of algorithms and advanced data structures.

Credits

7.5 ECTS

Topic

Graph Drawing

This course will give an introduction to the most important techniques and approaches for drawing graphs and networks. The focus is on algorithms, and hence the course enables the student to implement own graph layout tools. Graph Drawing is an important subfield of Information Visualization. It is of great practical relevance for many industrial applications, such as software development, analysis of biochemical networks, etc. (see above images).
Complex information can be better perceived by using visual representations. Graph Drawing is a way of representing structural information as diagrams of abstract graphs and networks, i.e., of a set of nodes and edges as well as additional information. The aim is to develop algorithms that produce aesthetically appealing drawings! We will discuss drawing algorithms for general (directed and undirected) graphs, but also for special graphs, such as trees or directed acyclic graphs. Among others, the course will cover force-directed methods, layered drawings, orthogonal drawings, and dynamic graphs. Also, popular graph drawing software is discussed.
Furthermore, this course presents an information visualization view on Graph Drawing, such as interaction techniques, exploration, and labelling.

Schedule

Preliminary Schedule:

#	Date	Topic	Slides
1	2009-11-04	Introduction
2	2009-11-11	Drawing of Trees
3	2009-11-20	Layered Drawings of Digraphs - Part I
4	2009-11-24	Layered Drawings of Digraphs - Part II
5	2009-12-02	Force-Directed Methods - Part I
6	2009-12-09	Force-Directed Methods - Part II
7	2009-12-16	Planarity Tests and Planarization
8	2010-01-12	Flow and Orthogonal Drawings
9	2010-01-13	An InfoVis View on Graph Drawing

Materials

Interestings URLs:

Graph Drawing Tools:

GDE Graph Editor or its successor Gryphon [restricted; don't distribute]
yEd Graph Editor
OGDF Open Graph Drawing Framework (C++)
Tulip - Graph Visualization Framework (C++)
Network Workbench (Java)
JUNG Java Universal Network/Graph Framework (Java)
Prefuse Visualization Toolkit (Java)

Assignments

Assignments consists of theoretical and practical exercices. They will be supervised by Ilir Jusufi. You can find general information about our assignments on the first assignment sheet.

Assignments:

Assignment 1 (Deadline: 2009-11-26; Exercise Date: 2009-11-27, 14:15-16:45, B3033)
Assignment 2 (Deadline: 2009-12-18; Exercise Date: 2009-12-18, 14:15-16:30, B3033)
NOTICE: For those unable to come at 2009-12-18, new presentation has been scheduled on 2009-12-17 from 15:00)
Assignment 3 (Deadline: 2010-01-12; Exercise Date: 2010-01-13, 09:00-12:00, B3033)

Groups:

Group A: Carles Garcia
Group B: Francisco Modesto
Group C: Yang Dingjie & Daniel Rüffer
Group D: Vladyslav Aleksakhin
Group E: Muhammad Asher

Further Courses

There are further interesting courses in Spring 10 that uses the knowledge of the Graph drawing course:

We permanently offer interesting topics for Bachelor's and Master's Theses that are related to graph drawing.