Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019
DOI: 10.7155/jgaa.00521
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.
|
Journal Supporters
|