Clustered Planarity with Pipes

A c-planar drawing that is not a c-planar drawing with pipes, even if the inter-cluster edges incident to the same cluster are consecutive (see the annuli around clusters), due to the presence of trivial block $(\mu, \nu)$

Abstract

In this paper we study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants of this problem in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm.

Type
Publication
Algorithmica
Giordano Da Lozzo
Assistant Professor (RTDa)

My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.