ICS Theory Group

ICS 269, Winter 2002: Theory Seminar

21 Feb 2003:
C-Planarity of Clustered Graphs
Jonathan Sun

I'll introduce the concepts, the open problem, and the progress that have been made. I'll touch some technical details in [1] and [4].


  1. Feng, Eades and Cohen, Clustered Graphs and C-planarity, Euro. Sym. on Alg. 1995.
  2. Dahlhaus, Linear time algorithms to recognize clustered planar graphs and its parallelization, LATIN'98.
  3. Duncan, Goodrich, and Kobourov, Planarity-Preserving Clustering and Embedding for Large Planar Graphs, Graph Drawing 1999.
  4. Battista, Walter Didimo and Marcandalli, Planarization of Clustered Graphs, Graph Drawing 2001.
  5. Gutwenger et al., Advances in C-Planarity Testing of Clustered Graphs, Graph Drawing 2002.