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