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

= Goals =

* generalization of force-directed/stress majorization layout approach to 3-uniform hypergraphs embedded in 3D space

14

* implementation of algorithm (recommended: Python)

15

* visualization in a suitable tool (recommended: Blender)

= Scope =

Master's Thesis

= Related Work/Literature =

22

23

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

24

25

[[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

26

27

[[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

28

29

30

= Involved Languages/Technologies =

* Python

* Blender

= Supervised by =