Available Topics - [Layout] Force-directed Layout of Hypergraphs in 3D Space 

Page / - last modified by Jette Petzold on 2024/02/13 07:58 

[Layout] Force-directed Layout of Hypergraphs in 3D Space 
last modified by Jette Petzold
on 2024/02/13 07:58

Table of Contents
Goals
Scope
Related Work/Literature
Involved Languages/Technologies
Supervised by

A relatively simple approach to drawing straightline graphs in a 2D plane is the force-directed approach. There are some variations in how the forces are modeled. One such variation is stress majorization.
A hypergraph is a graph where an edge is not restricted to connect only two vertices but may connect any number of nodes. A k-uniform hypergraph is a hypergraph where each edge is incident to k vertices. For this thesis we are only interested in 3-uniform hypergraphs.
There are several approaches to draw hypergraphs, but the typical approach is to transform them and ultimately draw them in a 2D plane. With this thesis we want to explore a more unconventional approach.
The set of edges of a graph are a binary relation on the set of its vertices. The set of edges of a 3-uniform hypergraph are a ternary relation on the set of its vertices. We call an edge in this hypergraph a tredge.
The goal is to implement a version of force-directed (or similar) layout for this type of hypergraphs within a three-dimensional space. Vertices are mapped to (x,y,z) coordinates and tredges should be mapped to triangular planes connecting the three incident vertices. Tredges should avoid intersecting similar to how edges should avoid crossing. The solution should be implemented in a suitable language such as python and a visualization should be created using the API of the open-source Blender tool. Blender provides us with an easy way to view and navigate 3D environments and therefore lends itself naturally to this task.
Goals
•	generalization of force-directed/stress majorization layout approach to 3-uniform hypergraphs embedded in 3D space
•	implementation of algorithm (recommended: Python)
•	visualization in a suitable tool (recommended: Blender)
Scope
Master's Thesis
Related Work/Literature
Thomas M. J. Fruchterman, Edward M. Reingold: Graph Drawing by Force-directed Placement. Softw. Pract. Exp. 21(11): 1129-1164 (1991)
Emden R. Gansner, Yehuda Koren, Stephen C. North: Graph Drawing by Stress Majorization. GD 2004: 239-250
Naheed Anjum Arafat, Stéphane Bressan: Hypergraph Drawing by Force-Directed Placement. DEXA (2) 2017: 387-394
Involved Languages/Technologies
•	Python
•	Blender
Supervised by
Maximilian Kasperowski
mka@informatik.uni-kiel.de