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 non-trivial cluster in C has at least two childcluster. This is the first time, this problem was investigated.


Actions:
Download: [img] Postscript
Download (268kB) | Preview
Download: [img] PDF
Download (206kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: [error in script] 0 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C40 Connectivity

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory

  • Uncontrolled Keywords: planar graphs, clustered graphs, c-planarity, triangulation, augmentation
    Subjects: 05-XX Combinatorics > 05Cxx Graph theory > 05C40 Connectivity
    05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 19 Dec 2002 00:00
    Last Modified: 12 Jan 2012 12:01
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 19 Dec 2002 00:00
    Last Modified: 12 Jan 2012 12:01
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/444