Work Package 05 of the GraDR EuroGIGA Project No. 10-EuroGIGA-OP-003.
In a clustered graph vertices are grouped into clusters, which can, in turn, be grouped into others clusters. More formally, a clustered graph (G,T) is a graph G together with a set T of clusters, that are recursively nested sets of vertices of G. 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 applications, such as the visualization of social networks.
A drawing of a clustered graph (G,T) is clustered-planar (c-planar) if the drawing of G is planar and each cluster is represented by a simple closed region that contains all and only the vertices of the cluster, that does not intersect other clusters, and that intersects each edge at most once. We are interested in the complexity of the c-planarity testing problem, that is, given a clustered graph, does it admit a c-planar drawing? The problem has unknown complexity and is one of the most studied problems in the graph drawing community during the last couple of years.
WP05 has three Milestones: M05.1 Identify classes of clustered graphs for which the problem can be efficiently solved. M05.2 Establish relationships between the problem and other problems known to be difficult. M05.3 Determine geometric representations of c-planar clustered graphs. That is, assuming that a clustered graph admits a c-planar drawing, find one of such drawings with straight-line edges, with good resolution, with clusters represented as convex polygons, etc.
A Methodological note. Possible lines of attack to the clustered planarity problem include determining significant classes of clustered graphs for which the problem can be efficiently solved or establishing relationships between the problem and other problems known to be difficult. A promising perspective is the one of exploring the relationship between clustered planarity and greedy drawings, where between any two vertices a path exists such that the Euclidean distance from an intermediate vertex to the destination decreases at every step. Such a relationship is expecially evident for Hamiltonian graphs. This creates interesting connections with WP09, that studies combinatorial aspects of geometric representations of graphs. Another problem that is related to clustered planarity is the simultaneous embedding with fixed edges problem, where two or more planar graphs on the same set of vertices are given and a planar drawing of each graph is requested such that a vertex has the same coordinates in all the drawings, edges are Jordan curves, and common edges are represented by the same curve. Determining the computational complexity of the simultaneous embedding with fixed edges problem could result in better understanding the computational complexity of clustered planarity.
Besides the Graph Drawing Group of the University of Roma Tre (coordinator), other groups of GraDR contribute actively to the WP05 Work Package: Prague, Dortmund, and Karlsruhe. In the list of publication of WP05 accessible from the present page the publications of such contributors are also listed.
On the other hand, the Grap Drawing Group of the University of Roma Tre contributes also to other Work Packages of the GraDR Project: WP01, WP02, WP03, WP04, WP08, and WP09.