DM876: Graph Drawing

Study Board of Science

Teaching language: Danish or English depending on the teacher
EKA: N340059102
Censorship: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master

STADS ID (UVA): N340059101
ECTS value: 5

Date of Approval: 02-10-2019


Duration: 1 semester

Version: Approved - active

Comment

New course spring 2020

Entry requirements

A Bachelor’s degree in Computer Science.

Academic preconditions

Students taking the course are expected to:

    • have knowledge of basic data structures

    • have knowledge of basic algorithms for processing data and manipulating data structures 

    • be able to determine the complexity of algorithms and to apply optimization strategies

Course introduction

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

Expected learning outcome

The learning objective of the course is that the student demonstrates the ability to:
    • 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 

Content

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

Literature

See Blackboard for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Spring

Tests

Oral exam

EKA

N340059102

Censorship

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card

Language

Normally, the same as teaching language

Examination aids

Allowed, a closer description of the exam rules will be posted under 'Course Information' on Blackboard.

ECTS value

5

Additional information

The exam consists of a number of practical assignments submitted during the course and a written examination.


Eksamensformen ved reeksamen kan være en anden end eksamensformen ved den ordinære eksamen. 

Indicative number of lessons

48 hours per semester

Teaching Method

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
  • Intro phase (lecture, class hours) - Hours: 24
  • training phase: Number of hours: 24, including examination hours 24
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.

Study phase activities:
  • Small projects aiming to visualize real world graph data sets by implementing learned graph drawing algorithms
  • Study of specialized graph drawing algorithms based on scientific papers

Teacher responsible

Name E-mail Department
Stefan Jänicke stjaenicke@imada.sdu.dk

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team at Registration & Legality

NAT

Recommended course of study

Profile Programme Semester Period