Universität zu Köln

Jünger, Michael, Leipert, Sebastian and Percan, Merijam (2002). Triangulating Clustered Graphs. Working Paper.

Preview

PDF zaik2002-444.pdf - Draft Version Download (206kB) | Preview

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.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Leipert, Sebastian UNSPECIFIED UNSPECIFIED UNSPECIFIED Percan, Merijam UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548686
Date:	2002
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54868