Triangulating Clustered Graphs
Jünger, Michael and Leipert, Sebastian and Percan, Merijam
(2002)
Triangulating Clustered Graphs.
Technical Report
, 7 p.
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 nontrivial cluster in C has at least two childcluster. This is the first time, this problem was investigated.
Download: 
Postscript
Download (268kB)  Preview 

Download: 
PDF
Download (206kB)  Preview 
Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  0 (Google Scholar)  
Uncontrolled Keywords:  planar graphs clustered graphs cplanarity triangulation augmentation 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zaik2002444 

Depositing User:  Prof. Dr. Michael Jünger 
Date Deposited:  19 Dec 2002 00:00 
Last Modified:  12 Jan 2012 12:01 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/444 