Overlapping Cluster Planarity

Abstract

This paper investigates a new direction in the area of cluster planarity by addressing the following question: Let G be a graph along with a hierarchy of vertex clusters, where clusters can partially intersect. Does G admit a drawing where each cluster is inside a simple closed region, no two edges intersect, and no edge intersects a region twice? We investigate the interplay between this problem and the classical cluster planarity testing problem where clusters are not allowed to partially intersect. Characterizations, models, and algorithms are discussed.