Advanced search
Start date

Interactive visualization and processing of large graphs

Grant number: 11/13724-1
Support type:Regular Research Grants
Duration: January 01, 2013 - December 31, 2014
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:José Fernando Rodrigues Júnior
Grantee:José Fernando Rodrigues Júnior
Home Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil


Graphs define complex data present in many research fields, so that extracting useful information from a graph structure can provide significant gains for various applications. However, new communications and monitoring technologies have produced graphs whose magnitudes hinder their computation and analysis. Among the processes used to handle such graphs is the hierarchical partitioning; according to this methodology, the vertices of a graph can be grouped recursively, determining a hierarchy, according to the relationships defined by its own edges. Still, the current data structures used for this computation are based on primary memory, limiting the possibilities of using a scarce resource compared to the volumes of data. Therefore, this project aims at the research and development of a new methodology for representing hierarchically partitioned graphs. The new methodology shall allow the processing of graphs stored on disk while allowing it to answer to connectivity queries over the original graph and over the partitions of the hierarchical representation. As a proof of concept, the proposed innovation will be applied to a system of multi-resolution visualization of graphs called GMine. The new approach will allow alternatives less subject to the cardinality of these sets of data. (AU)