"Triangulating Clustered Graphs"
Technical report by Michael Jünger, Sebastian Leipert, Merijam Percan, available as BibTeX Source, postscript file, compressed postscript file and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2002-444
Keywords:	augmentation, clustered graphs, c-planarity, planar graphs, triangulation
MSC codes:	05C10, 05C40
This technical report has 7 pages, was written in December 2002, it has not been published.
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. As we triangulate a planar embedded graph so that G is still planar embedded after triangulation, we consider triangulation of a c-connected clustered graph that preserve the c-planar embedding. In this paper, we provide a linear time algorithm for triangulating c-connected c-planar embedded clustered graphs C=(G,T) so that C is still c-planar embedded after triangulation. We assume that every non-trivial cluster in C has at least two childcluster. This is the first time, this problem was investigated.