1. Drawing Clustered Planar Graphs on Disk Arrangements
- Author
-
Mchedlidze, Tamara, Radermacher, Marcel, Rutter, Ignaz, Zimbel, Nina, Visualisation and Graphics, Sub Visualisation and Graphics, Visualisation and Graphics, and Sub Visualisation and Graphics
- Subjects
Combinatorics ,symbols.namesake ,Computational Theory and Mathematics ,General Computer Science ,Computer science ,symbols ,Geometry and Topology ,Computer Science Applications ,Theoretical Computer Science ,Planar graph - Abstract
Let G = (V, E) be a planar graph and let V be a partition of V . We refer to the graphs induced by the vertex sets in V as clusters. Let DC be an arrangement of pairwise disjoint disks with a bijection between the disks and the clusters. Akitaya et al. [2] give an algorithm to test whether (G, V) can be embedded onto DC 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. [3] who solely consider biconnected clusters. Moreover, we prove that it is N Phard 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. [4]
- Published
- 2020