Clustered Planarity

Definition

A graph is cluster planar if there is a planar drawing of it where we can also add its clusters as closed regions that only cross the edges that leave the respective cluster.

Formally, given a graph \(G=(V,E)\) equipped with a cluster hierarchy \(T\), which is a rooted tree with the vertices \(V\) as leaves. Each inner node \(\mu\) of \(T\) represents a cluster encompassing all leaves \(V_\mu\) of the subtree rooted at \(\mu\). A cluster planar drawing is a planar drawing that also maps every cluster \(\mu\) to a simple closed region \(R_\mu\) such that

  1. \(R_\mu\) encloses exactly the vertices \(V_\mu\),
  2. no two cluster region boundaries intersect, and
  3. no edge intersects the boundary of a cluster more than once. A cluster graph is cluster planar if it admits a cluster planar drawing.

Background

Lengauer (1989) studied and solved this problem as early as 1989 in the setting where the clusters are connected. Feng, Cohen, and Eades (1995), who coined the term Clustered Planarity, rediscovered this algorithm and asked the general question where disconnected clusters are allowed. This question remained open for 30 years. In that time, polynomial-time algorithms were found for many special-cases (Angelini and Da Lozzo 2019; Cortese et al. 2008; Fulek et al. 2015; Gutwenger et al. 2002) before Fulek and Tóth (2022) found an \(O((n+d)^8)\) solution in 2019, where \(d\) is the number of crossings between a cluster-border and an edge leaving the cluster. Subsequently, Bläsius, Fink, and Rutter (2023) gave a solution via Synchronized Planarity with a running time of \(O((n+d)^2)\), which also reveals the main concepts for solving Clustered Planarity.

Complexity

Let \(d\) be the number of edge-cluster boundary crossings and \(\Delta\) be the maximum number of edges crossing a single cluster border. While there are no direct solutions to the problem, Clustered Planarity can be solved in time…

All these reductions use the cd-Tree representation of Clustered Planarity (Bläsius and Rutter 2016). As the reduction subdivides an edge for each cluster boundary it crosses, the representation has size \(O(n+d)\).

Clustered Planarity also reduces to SEFE-2 by representing the cluster boundary, where the order of edges leaving needs to correspond to the order of the same edges entering, via a gadget (Schaefer 2013, Theorem 6.17; see also Rutter 2020, sec. 13.2.2).

\(\langle \alpha, \beta, \gamma \rangle\)-drawings are a generalization of Clustered Planarity, where given counts of edge-edge, cluster-cluster, and cluster-edge crossings are allowed (Angelini et al. 2015).

See also

References

Angelini, Patrizio, and Giordano Da Lozzo. 2019. “Clustered Planarity with Pipes.” Algorithmica 81 (6): 2484–2526. https://doi.org/10.1007/s00453-018-00541-w.
Angelini, Patrizio, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli. 2015. “Relaxing the Constraints of Clustered Planarity.” Computational Geometry 48 (2): 42–75. https://doi.org/10.1016/j.comgeo.2014.08.001.
Bläsius, Thomas, Simon D. Fink, and Ignaz Rutter. 2023. “Synchronized Planarity with Applications to Constrained Planarity Problems.” ACM Transactions on Algorithms. https://doi.org/10.1145/3607474.
Bläsius, Thomas, and Ignaz Rutter. 2016. “A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem.” Theoretical Computer Science 609: 306–15. https://doi.org/10.1016/j.tcs.2015.10.011.
Cortese, Pier Francesco, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Maurizio Pizzonia. 2008. “C-Planarity of c-Connected Clustered Graphs.” Journal of Graph Algorithms and Applications 12 (2): 225–62. https://doi.org/10.7155/jgaa.00165.
Feng, Qing-Wen, Robert F. Cohen, and Peter Eades. 1995. “Planarity for Clustered Graphs.” In Proceedings of the 3rd Annual European Symposium on Algorithms (ESA’95), edited by Paul G. Spirakis, 979:213–26. LNCS. Springer. https://doi.org/10.1007/3-540-60313-1_145.
Fink, Simon D., and Ignaz Rutter. 2023. “Maintaining Triconnected Components Under Node Expansion.” In Proceedings of the 13th Conference on Algorithms and Complexity (CIAC’23), edited by Marios Mavronicolas, 13898:202–16. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-031-30448-4_15.
Fulek, Radoslav, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. 2015. “Clustered Planarity Testing Revisited.” The Electronic Journal of Combinatorics 22 (4). https://doi.org/10.37236/5002.
Fulek, Radoslav, and Csaba D. Tóth. 2022. “Atomic Embeddability, Clustered Planarity, and Thickenability.” Journal of the ACM 69 (2): 13:1–34. https://doi.org/10.1145/3502264.
Gutwenger, Carsten, Michael Jünger, Sebastian Leipert, Petra Mutzel, Merijam Percan, and René Weiskircher. 2002. “Advances in c-Planarity Testing of Clustered Graphs.” In Proceedings of the 10th International Symposium on Graph Drawing (GD’02), edited by Stephen G. Kobourov and Michael T. Goodrich, 2528:220–35. LNCS. Springer. https://doi.org/10.1007/3-540-36151-0_21.
Lengauer, Thomas. 1989. “Hierarchical Planarity Testing Algorithms.” Journal of the ACM 36 (3): 474–509. https://doi.org/10.1145/65950.65952.
Patrignani, Maurizio. 2013. “Planarity Testing and Embedding.” In Handbook on Graph Drawing and Visualization, edited by Roberto Tamassia, 1–42. Chapman; Hall/CRC. https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/planarity.pdf.
Rutter, Ignaz. 2020. “Simultaneous Embedding.” In Beyond Planar Graphs, edited by Seok-Hee Hong and Takeshi Tokuyama, 237–65. Springer Singapore. https://doi.org/10.1007/978-981-15-6533-5_13.
Schaefer, Marcus. 2013. “Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants.” Journal of Graph Algorithms and Applications 17 (4): 367–440. https://doi.org/10.7155/jgaa.00298.