Special Issue on Selected Papers from the 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019
Drawing Clustered Planar Graphs on Disk Arrangements
Vol. 24, no. 2, pp. 105-131, 2020. Regular paper.
Abstract Let $G=(V, E)$ be a planar graph and let $\mathcal V$ be a partition of $V$. We refer to the graphs induced by the vertex sets in $\mathcal V$ as clusters. Let $\mathcal C_{\mathcal C}$ be an arrangement of pairwise disjoint disks with a bijection between the disks and the clusters. Akitaya et al.[Akytaia et al. SODA 2018] give an algorithm to test whether $(G, \mathcal V)$ can be embedded onto $\mathcal C_{\mathcal C}$ with the additional constraint that edges are routed through a set of pipes between the disks. If such an embedding exists, we prove that every clustered graph and every disk arrangement without pipe-disk intersections has a planar straight-line drawing where every vertex is embedded in the disk corresponding to its cluster. This result can be seen as an extension of the result by Alam et al.[Alam et al. JGAA 2015] who solely consider biconnected clusters. Moreover, we prove that it is $\mathcal{NP}$-hard to decide whether a clustered graph has such a straight-line drawing, if we permit pipe-disk intersections, even if all disks have unit size. This answers an open question of Angelini et al.[Angelini et al. GD 2014].
Submitted: April 2019.
Reviewed: June 2019.
Revised: July 2019.
Accepted: September 2019.
Final: February 2020.
Published: February 2020.
article (PDF)