Splitting Clusters to Get C-Planarity
Angelini, Patrizio and Frati, Fabrizio and Patrignani, Maurizio (2010) Splitting Clusters to Get C-Planarity. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 57-68 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_8).
Full text not available from this repository.
In this paper we introduce a generalization of the c-planarity testing problem for clustered graphs. Namely, given a clustered graph, the goal of the S PLIT-C-P LANARITY problem is to split as few clusters as possible in order to make the graph c-planar. Determining whether zero splits are enough coincides with testing c-planarity. We show that S PLIT-C-P LANARITY is NP-complete for c-connected clustered triangulations and for non-c-connected clustered paths and cycles. On the other hand, we present a polynomial-time algorithm for ﬂat c-connected clustered graphs whose underlying graph is a biconnected seriesparallel graph, both in the ﬁxed and in the variable embedding setting, when the splits are assumed to maintain the c-connectivity of the clusters.
Repository Staff Only: item control page