Algorithms and Models for Hybrid Representations of large Locally-Dense Networks

01/04/2018 to 31/03/2020

The project will study hybrid representations of locally-dense networks. It is widely accepted that most real-world networks (for example most social networks and the Internet) consist of subnetworks which are strongly connected internally and do not have many connections among them. Hybrid representations use different drawing standards for the visualization of the local densities of the network and of the sparse graph structure interconnecting them. The main goal of the project is to design algorithms for the construction of hybrid representations with provable theoretical guarantees on their readability, thus contributing to bridging the gap between theory and practice in Network Visualization.
Work on hybrid representations of locally-dense graphs has been initiated in 2007 by Henry et al., who introduced the NodeTrix model, using matrices for the dense parts and links among the matrices for the sparse high-level structure. While the purpose of this work was purely applicative, with the realization of an interaction tool to construct and edit representations of this type, a theoretical approach to this visualization has been first proposed in two papers, appeared in GD 2015 and GD 2016, coauthored by members of this project. The first one introduced the intersection-link model (M1 in this project), where vertices are rectangles, the dense parts are represented by intersections, and the sparse structure by links. In the second paper, the model is the same as in NodeTrix (M2 in this project). In both cases, the final goal is to provide algorithms to construct crossing-free representations.
In this project we will conduct a systematic study of the theory behind hybrid representations, facing a variety of algorithmic and combinatorial problems. On one hand, we will rely on the deep geometric and topological properties of planar graphs discovered through the centuries; on the other hand, we will move in an unexplored area of research: we will hence confront novel challenges for which we will contrive original solutions. We will implement our algorithms to provide a system that allows a user to manually interact with the dense subnetworks while a readable representation of the sparse part of the network is automatically constructed.
The collaboration between the research groups at Tübingen and Roma Tre universities, as well as the one between the German and Italian PIs, has solid roots, with several success stories during the years. The rest of the team will consist of two PhD students from the German side and of two young post-docs from the Italian side.