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

1

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

2

3

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.

4

5

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.

6

7

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

8

9

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>>https://www.blender.org/]] tool. Blender provides us with an easy way to view and navigate 3D environments and therefore lends itself naturally to this task.

10

11

12

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.

13

14

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

19

* implementation of algorithm (recommended: Python)

20

* visualization in a suitable tool (recommended: Blender)

= Scope =

Master's Thesis

= Related Work/Literature =

27

28

[[Thomas M. J. Fruchterman>>url:https://dblp.org/pid/39/1546.html]], [[Edward M. Reingold>>url:https://dblp.org/pid/r/EMReingold.html]]: Graph Drawing by Force-directed Placement. [[Softw. Pract. Exp. 21(11)>>url:https://dblp.org/db/journals/spe/spe21.html#FruchtermanR91]]: 1129-1164 (1991)

29

30

[[Emden R. Gansner>>url:https://dblp.org/pid/35/6095.html]], [[Yehuda Koren>>url:https://dblp.org/pid/k/YehudaKoren.html]], [[Stephen C. North>>url:https://dblp.org/pid/n/StephenCNorth.html]]: Graph Drawing by Stress Majorization. [[GD 2004>>url:https://dblp.org/db/conf/gd/gd2004.html#GansnerKN04]]: 239-250

31

32

[[Naheed Anjum Arafat>>url:https://dblp.org/pid/204/2502.html]][[image:https://dblp.org/img/orcid-mark.12x12.png]], [[Stéphane Bressan>>url:https://dblp.org/pid/b/SBressan.html]]: Hypergraph Drawing by Force-Directed Placement. [[DEXA (2) 2017>>url:https://dblp.org/db/conf/dexa/dexa2017-2.html#ArafatB17]]: 387-394

33

34

35

= Involved Languages/Technologies =

* Python

* Blender

= Supervised by =