Description
From social media to multi-omics interaction analyses, modern network visualization deals with increasingly large and dense (sub-)networks. These networks are most commonly visualized as straight-line node-link 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 force-directed 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 hard-to-read, or even completely unintelligible, drawings; so-called “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 non-theoreticians 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 lower-level 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 24-26, 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 Jean-Daniel Fekete. "Improving the readability of clustered social networks using node duplication." IEEE Transactions on Visualization and Computer Graphics 14.6 (2008): 1317-1324.
-
Eades, Peter, and C. F. X. de Mendonça N. "Vertex splitting and tension-free layout." Graph Drawing: Symposium on Graph Drawing, GD'95 Passau, Germany, September 20–22, 1995 Proceedings 3. Springer Berlin Heidelberg, 1996.