# Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract)

Gutwenger, Carsten and Jünger, Michael and Leipert, Sebastian and Mutzel, Petra and Percan, Merijam and Weiskircher, René (2002) Advances in C-Planarity Testing of Clustered Graphs (Extended Abstract). In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002 , pp. 220-235(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_21).

Full text not available from this repository.

## Abstract

A clustered graph C=(G,T) consists of an undirected graph G and a rooted tree T in which the leaves of T correspond to the vertices of G=(V,E). Each vertex \mu in T corresponds to a subset of the vertices of the graph called "cluster". c-planarity is a natural extension of graph planarity for clustered graphs, and plays an important role in automatic graph drawing. The complexity status of c-planarity testing is unknown. It has been shown in [FCE95,Dah98] that c-planarity can be tested in linear time for c-connected graphs, i.e., graphs in which the cluster induced subgraphs are connected. In this paper, we provide a polynomial time algorithm for c-planarity testing of "almost" c-connected clustered graphs, i.e., graphs for which all nodes corresponding to the non-c-connected clusters lie on the same path in T starting at the root of T, or graphs in which for each non-connected cluster its super-cluster and all its siblings in T are connected. The algorithm is based on the concepts for the subgraph induced planar connectivity augmentation problem presented in [GJL+02]. We regard it as a first step towards general c-planarity testing.

Item Type: Conference Paper 10.1007/3-540-36151-0_21 G Algorithms and Complexity > G.490 EmbeddingsM Methods > M.600 PlanarG Algorithms and Complexity > G.770 Planarity TestingG Algorithms and Complexity > G.350 Clusters http://gdea.informatik.uni-koeln.de/id/eprint/248