PRIN-2022, Unifi
UNIFI Research Unit: Andrea Marino
project led by: Università degli Studi di Perugia (PI: Fabrizio Montecchiani Sulis), in collaboration with LUISS (RU:Irene Finocchi) and Università Roma 3 (RU: Fabrizio Frati)
Brief description of the proposal
Graph-based models are pervasive in many fields of science and technology and their visualization plays a crucial role in the analysis and exploration of complex datasets. In this scenario, graph drawing is a key research area whose ultimate goal is to construct valuable visualizations of graphs and networks. Despite a great effort over the last thirty years, the problem of computing effective visualizations remains a largely elusive and pressing one. The objective of project NextGRAAL is to develop new algorithmic results and novel visualization paradigms that will provide the scientific groundwork for the next generation of software and tools, which will be able to efficiently compute high-quality graph visualizations with application-driven constraints of various kinds. Besides methodological contributions, the project will experimentally validate the algorithmic solutions on two relevant application domains and will be consequently organized into two main workparts.
WP1: Algorithmic methodologies with theoretical guarantees for constrained graph visualization and exploration. We plan to exploit parameterized and exact algorithms, possibly coupled with complexity lower bounds, to efficiently compute provably-good solutions for hard problems dealing with constrained graph layouts. We will also pioneeringly design enumeration algorithms to explore solutions stemming from layout problems with relaxed constraints.
WP2: Validation of algorithmic solutions for constrained graph visualization and exploration. While our algorithms can be beneficial for multiple applications, we will validate them on two relevant scenarios, i.e., socio-semantic and transportation networks. Exploring the former brings together the study of two intertwined data generation processes: a social community and a content-creation process. Visualizing the latter is crucial to make complex infrastructures easily accessible to a broad set of users.
Impact. Given the ubiquity of graphs in science and technology, as well as the key role of visualization in graph processing pipelines, NextGRAAL has a great potential to make a strong impact on research, industry, and society.
Research team and budget. The project is participated by 4 research units: UniPG, UniFI, LUISS, UniRM3. All researchers share a common algorithmic background and yet provide fundamental and complementary expertise on the research topics and methodologies involved in the project. The project budget will be mostly devoted to recruiting young researchers; other resources are either already available (e.g. lab hardware and software) or will be charged to the overhead.