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 , 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 flat c-connected clustered graphs whose underlying graph is a biconnected seriesparallel graph, both in the fixed and in the variable embedding setting, when the splits are assumed to maintain the c-connectivity of the clusters.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-11805-0_8
Classifications: P Styles > P.180 Cluster
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.540 Planar
G Algorithms and Complexity > G.840 Planarization
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1062

Actions (login required)

View Item View Item