Models and algorithms to compute drawings of clustered graphs.
The purpose of this topic is the study of algorithms for the visualization of clustered graphs. In a clustered graph vertices are grouped into clusters, which can, in turn, be grouped into others clusters. This model can be effectively applied to represent graphs at different levels of abstractions, showing semantic relations between vertices, and making easy the navigation of large graphs. Drawing clustered graphs is required in many application, as the visualization of networks, information systems, and social networks.
Many research interests in the field of clustered graphs are devoted to the problem of cluster-planarity (c-planarity) testing; namely, a c-planarity test is an algorithm to state if a clustered graphs admits a drawing such that the clusters lie in disjoint regions and there are not edges crossings and edge-region crossings. The computational complexity of the c-planarity testing is still unknown. It has been proved that the problem can be solved in polynomial time only if each cluster induces a connected subgraph, or if the clustered graph belongs to specific families.