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

Last modified by Maximilian Kasperowski on 2025/08/06 08:37
Export
Office Formats
Export as PDF Export as ODT Export as RTF
Other Formats

Select the pages to export:

select all/ none

Legend:
  Created Page
  Modified Extension Page
  Clean Extension Page

Export as HTML

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.

This type of visualization could be used to explore ternary relationships. These are somewhat unusual but some practical examples do exist for example student submission groups of 3 across multiple modules. In this case each tredge marks a submission group for a particular course.

Another example is the visualization of triad chords in music.

# 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

Tags:
Created by Maximilian Kasperowski on 2024/02/06 15:15

- Comments (0)
- Attachments (1)
- History
- Information

# Quick Links

KIELER on GitHub
RTSYS Homepage

XWiki 14.4.7