Details

Type

Master Thesis

Persons

1

Description

Graphs are commonly laid out as node-link diagrams, in which nodes are represented as (labeled) circles and edges as straight lines connecting them. However, depending on the particular force-directed or spring-embedded layout algorithm chosen, the resulting drawing can look wildly different. These differences can be quantified using various so-called quantitative graph aesthetic metrics, such as the number of edge crossings, edge crossing angles, or node/edge orthogonality. In this project, you will implement multiple common layout algorithms, such as Fruchterman-Reingold and Kamada-Kawai, in order to evaluate how they differ in terms of several selected graph aesthetic metrics.

Tasks

  • Implement several graph layout algorithms
  • Implement several graph aesthetic metrics
  • Evaluate layouts algorithms for multiple simulated and real datasets
  • Potentially evaluate effect of layout on real humans

Requirements

  • Knowledge of English language (source code comments and final report should be in English)
  • Knowledge of C++ or Rust
  • Interest or Knowledge in Graph Drawing

Environment

The project should be implemented as a standalone application, desktop or web-based (to be discussed).

Responsible

For more information please contact Henry Ehlers, Renata Raidou.