Overlapping Cluster Planarity - Didimo, Walter; Giordano, Francesco; Liotta, Giuseppe (Journal of Graph Algorithms and Applications, 2008)
This paper investigates a new direction in the area of cluster planarity byaddressing the following question: Let G be a graph along with ahierarchy of vertex clusters, where clusters can partiallyintersect. Does G admit a drawing where each cluster is inside asimple closed region, no two edges intersect, and no edgeintersects a region twice? We investigate the interplay betweenthis problem and the classical cluster planarity testing problemwhere clusters are not allowed to partially intersect.Characterizations, models, and algorithms are discussed. <!---->