Splitting Clusters to Get CPlanarityAngelini, Patrizio and Frati, Fabrizio and Patrignani, Maurizio (2010) Splitting Clusters to Get CPlanarity. In: Graph Drawing 17th International Symposium, GD 2009, September 2225, 2009 , pp. 5768(Official URL: http://dx.doi.org/10.1007/9783642118050_8). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642118050_8
AbstractIn this paper we introduce a generalization of the cplanarity testing problem for clustered graphs. Namely, given a clustered graph, the goal of the S PLITCP LANARITY problem is to split as few clusters as possible in order to make the graph cplanar. Determining whether zero splits are enough coincides with testing cplanarity. We show that S PLITCP LANARITY is NPcomplete for cconnected clustered triangulations and for noncconnected clustered paths and cycles. On the other hand, we present a polynomialtime algorithm for ﬂat cconnected 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 cconnectivity of the clusters.
Actions (login required)
