Description
From social media to multiomics interaction analyses, modern network visualization deals with increasingly large and dense (sub)networks. These networks are most commonly visualized as straightline nodelink diagrams, which illustrate entities as points of potentially different shapes or colors, and edges as straight lines connecting them. If not drawn by hand, such graphs are commonly laid out using forcedirected layout algorithms, owing to their implementations’ availability and computational tractability. However, these techniques do not scale well visually to dense and/or larger graphs, producing hardtoread, or even completely unintelligible, drawings; socalled “hairballs”. One key factor which contributes to the poor readability of these “hairballs” is the number of edge crossings. While edge crossings can be eliminated through the outright removal of edges or nodes, this is not a useful paradigm in practice, as nontheoreticians are interested in all relationships and entities in their data. Here, we are interested in investigating the resolution of edge crossings through the (iterative) splitting of nodes instead, dividing all incoming and outgoing edges of the original nodes across its split copies such that the number of edge crossings is minimized.
Tasks
In this project you will be tasked with designing, implementing, and quantitatively evaluating an algorithm for the minimization of edge crossings through vertex splitting. Your approach should be scalable to hundreds of nodes and thousands of edges, if possible.
Requirements
 Knowledge of English language (source code comments and final report should be in English)
 Knowledge of C++ or comparably lowerlevel programming languages is advantageous
 Knowledge of and interest in information and graph visualization
Environment
The project should be implemented as a standalone application.
References

Kobourov, Stephen G., Sergey Pupyrev, and Bahador Saket. "Are crossings important for drawing large graphs?." Graph Drawing: 22nd International Symposium, GD 2014, Würzburg, Germany, September 2426, 2014, Revised Selected Papers 22. Springer Berlin Heidelberg, 2014.

Nöllenburg, Martin, et al. "Planarizing graphs and their drawings by vertex splitting." International Symposium on Graph Drawing and Network Visualization. Cham: Springer International Publishing, 2022.

Henry, Nathalie, Anastasia Bezerianos, and JeanDaniel Fekete. "Improving the readability of clustered social networks using node duplication." IEEE Transactions on Visualization and Computer Graphics 14.6 (2008): 13171324.

Eades, Peter, and C. F. X. de Mendonça N. "Vertex splitting and tensionfree layout." Graph Drawing: Symposium on Graph Drawing, GD'95 Passau, Germany, September 20–22, 1995 Proceedings 3. Springer Berlin Heidelberg, 1996.