DM876: Graph Drawing

The aim of the course is to enable the student to apply and implement graph drawing algorithms in order to visualize graph-theoretical features accordingly. The course provides an overview of graph drawing algorithms to be applied for diverse graph types such as trees, directed and undirected graph. In addition, aesthetic criteria and strategies to visualize structural features of graphs appropriately are discussed. This is important as graph structures are fundamental to many research areas such as social network theory, biology and cartography, and their visualization is important for domain experts to understand topological features of graphs necessary for verifying and generating hypotheses on the researched subject.

The course builds on the knowledge acquired in the courses DM550 (Introduction to Programming), DM507 (Algorithms and Data Structures) and DM553 (Complexity and Computability), and gives an academic basis for preparing a master thesis in which graph structures are focused.

In relation to the competence profile of the degree it is the explicit focus of the course to:

    • provide expert knowledge on a selected area of study that is related to a high bandwidth of research fields

    • give the competence to describe graph drawing algorithms presented during the course 

    • give skills to apply learned graph drawing algorithms adequately

    • give the competence to adapt graph drawing algorithms according to application requirements, including the ability to decide on layout constraints and visual features

    • give the competence to transfer learned algorithms to different application areas

    • challenge the student with real-life datasets and problem solving skills

    • describe how graph drawing algorithms operate

    • choose appropriate graph drawing algorithms for given graphs

    • consider aesthetic criteria when drawing graphs

    • implement graph drawing algorithms

    • adapt standard graph drawing algorithms for occurring data anomalies

    • discover bottlenecks in graph drawing algorithms and apply optimization strategies

    • design and implement interfaces for graph visualization 

The following main topics are contained in the course:

    • graph embeddings, planarity testing and planarization of graphs

    • aesthetic criteria to be considered when drawing graphs

    • straight-line, orthogonal, rectangular and polyline drawing algorithms

    • force-directed drawing algorithms

    • hierarchical drawing algorithms

    • tree drawing algorithms

    • miscellaneous graph drawings, e.g., radial layouts, arc diagrams, product graph drawings, topological graph layout

    • applications of graph drawing algorithms in various research areas, e.g., biology, cartography, data analytics and digital humanities

    • visual features to be used for conveying graph-theoretical features in a visual form

    • implemention of selected graph drawing algorithms

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.

The intro phase facilitates the introduction to new material and topics, which in the skills training phase are processed with exercises prepared at home and discussed in class to validate the acquired knowledge. The study activity in form of practical applications gives the students the possibility to apply and use the knowledge acquired.