Clustered planarity

A clustered planar drawing

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]

The clustering can be described combinatorially by a collection of subsets of the vertices such that, for each two subsets, either both are disjoint or one is contained in the other. It is not required that the clustering be maximal nor that every vertex belong to a cluster. In a clustered planar drawing, 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]

Unsolved problem in computer science:
Can the existence of a clustered planar drawing for a given clustered graph be tested in polynomial time?
(more unsolved problems in computer science)

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 planarity 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

  1. 1 2 Cortese, Pier Francesco; Di Battista, Giuseppe (2005), "Clustered planarity", Proc. 21st Symp. Computational Geometry (SCG'05), New York: ACM, pp. 32–34, doi:10.1145/1064092.1064093, MR 2460345. A brief survey paper associated with an invited talk at SCG.
  2. 1 2 3 4 Cortese, Pier Francesco; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Pizzonia, Maurizio (2008), "C-planarity of C-connected clustered graphs", Journal of Graph Algorithms and Applications, 12 (2): 225–262, doi:10.7155/jgaa.00165, MR 2448402.
  3. ↑ Feng, Qing-Wen; Cohen, Robert F.; Eades, Peter (1995), "Planarity for clustered graphs", Algorithms – ESA '95: Third Annual European Symposium, Corfu, Greece, September 25–27, 1995, Proceedings, Lecture Notes in Computer Science, 979, Springer, pp. 213–226, doi:10.1007/3-540-60313-1_145.
  4. ↑ Lengauer, Thomas (1989), "Hierarchical planarity testing algorithms", Journal of the ACM, 36 (3): 474–509, doi:10.1145/65950.65952, MR 1072234. A preliminary version of these results was announced earlier at the 13th International Colloquium on Automata, Languages and Programming (ICALP '86), doi:10.1007/3-540-16761-7_71, MR 0864684.
  5. ↑ Dahlhaus, Elias (1998), "A linear time algorithm to recognize clustered planar graphs and its parallelization", LATIN'98: Theoretical Informatics (Campinas, 1998), Lecture Notes in Computer Science, 1380, Springer, Berlin, pp. 239–248, doi:10.1007/BFb0054325, MR 1635460.
  6. ↑ Gutwenger, Carsten; Jünger, Michael; Leipert, Sebastian; Mutzel, Petra; Percan, Merijam; Weiskircher, René (2002), "Advances in C-planarity testing of clustered graphs (extended abstract)", Graph Drawing: 10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers, Lecture Notes in Computer Science, 2528, Springer, Berlin, pp. 220–235, doi:10.1007/3-540-36151-0_21, MR 2063426.
This article is issued from Wikipedia - version of the 9/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.