Overlapping Cluster Planarity
Walter Didimo, Francesco Giordano, and Giuseppe Liotta
Vol. 12, no. 3, pp. 267-291, 2008. Regular paper.
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.
Submitted: April 2007.
Reviewed: July 2007.
Revised: December 2007.
Accepted: January 2008.
Final: February 2008.
Published: October 2008.
Communicated by Seok-Hee Hong
article (PDF)