Triangulating Clustered Graphs

Jünger, Michael and Leipert, Sebastian and Percan, Merijam (2002) Triangulating Clustered Graphs.
Technical Report , 7 p.


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.

Download: [img] Postscript
Download (268kB) | Preview
Download: [img] PDF
Download (206kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2002-444
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 19 Dec 2002 00:00
Last Modified: 12 Jan 2012 12:01