Clustered planarity

In graph drawing, a clustered planar graph is a graph together with a hierarchical clustering on its vertices, such that the graph drawn together with a collection of simple closed curves surrounding each cluster, so that there are no crossings between graph edges or clusters.^[1] More precisely, no two edges may cross each other (that is, the graph must be planar), no two of the curves representing clusters may cross each other, an edge may cross a cluster boundary only if it connects a vertex inside the cluster to a vertex outside the cluster, and when an edge and cluster boundary cross they may cross only once.^[1] It is unknown whether it is possible to construct clustered planar drawings in polynomial time. However, many special cases have polynomial time algorithms.^[2]

Connected clusters

The clustered planarity problem was introduced by Feng, Cohen & Eades (1995), who posed the general problem but gave a polynomial time algorithm only for the special case in which each cluster forms a connected subgraph of the input graph. Their algorithm processes the clustering hierarchy in bottom-up order, using PQ tree data structures to represent the possible orderings of the edge crossings around each cluster boundary.^[3]

Later, Cortese & Di Battista (2005) observed that an earlier paper by Lengauer (1989) also contained very similar results. Lengauer was primarily interested in testing planarity of graphs defined by graph rewriting schemes, but his algorithm can also be used to test clustered plnarity in the connected case.^[4] Although the running time of Lengauer's algorithm is linear in its input size, it only gives a quadratic time algorithm for clustered planarity, because the graph rewriting description of the input can be significantly larger than the data needed to describe a clustered planarity instance.^[2] Dahlhaus (1998) claimed a linear time algorithm for connected clustered planarity, but did not provide full details;^[5][2] a later linear time algorithm was given by Cortese et al. (2008).^[2]

Other special cases

As well as the case of connected clustered planarity, many other special cases are now known to have polynomial time algorithms. For instance, Gutwenger et al. (2002) described polynomial time algorithms for "almost connected" clustered graphs in which either the disconnected clusters all lie along a single root-to-leaf path of the cluster hierarchy, or each disconnected cluster has connected parent and siblings.^[6]

Cortese et al. (2008) survey other solved cases of clustered planarity. These include the case in which there are only two clusters, forming a partition of the vertices, the case in which the underlying graph and a certain incidence relation between the clusters are both cycles, the case in which the hierarchy is flat (all clusters are at the same level) and the graph is embedded with at most five vertices per face, and the case in which each disconnected cluster has a connected parent and an edge connecting each connected component to something outside the cluster.

References