ALCOMFT-TR-03-97

Michael Jünger, Sebastian Leipert and Merijam Percan
Triangulating Clustered Graphs
Cologne. Work package 4. November 2003.

Abstract: In this paper, we provide a linear time algorithm for triangulating c-connected c-planar embedded clustered graphs C=(G,T) so that C ist still c-planar embedded after triangulation. We assume that every non-trivial cluster in C has at least two child cluster. This is the first time, this problem was investigated.

Postscript file: ALCOMFT-TR-03-97.ps.gz (106 kb).