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).