Cluster planarity is currently recognized as one of the most interesting problem in graph drawing. This paper investigates a new direction in this area 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.
Overlapping Cluster Planarity
DIDIMO, WALTER;GIORDANO, FRANCESCO;LIOTTA, Giuseppe
2007
Abstract
Cluster planarity is currently recognized as one of the most interesting problem in graph drawing. This paper investigates a new direction in this area 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
