Advances in CPlanarity 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 CPlanarity Testing of Clustered Graphs (Extended Abstract). In: Graph Drawing 10th International Symposium, GD 2002, August 2628, 2002 , pp. 220235(Official URL: http://dx.doi.org/10.1007/3540361510_21). This is the latest version of this item.
Official URL: http://dx.doi.org/10.1007/3540361510_21
AbstractA 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". cplanarity is a natural extension of graph planarity for clustered graphs, and plays an important role in automatic graph drawing. The complexity status of cplanarity testing is unknown. It has been shown in [FCE95,Dah98] that cplanarity can be tested in linear time for cconnected graphs, i.e., graphs in which the cluster induced subgraphs are connected. In this paper, we provide a polynomial time algorithm for cplanarity testing of "almost" cconnected clustered graphs, i.e., graphs for which all nodes corresponding to the noncconnected clusters lie on the same path in T starting at the root of T, or graphs in which for each nonconnected cluster its supercluster 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 cplanarity testing.
Available Versions of this Item
Actions (login required)
