A new perspective on clustered planarity as a combinatorial embedding problem

T. Blaesius, I. Rutter

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)

Abstract

The clustered planarity problem (c-planarity) asks whether a hierarchically clustered graph admits a planar drawing such that the clusters can be nicely represented by regions. We introduce the cd-tree data structure and give a new characterization of c-planarity. It leads to efficient algorithms for c-planarity testing in the following cases. (i) Every cluster and every co-cluster (complement of a cluster) has at most two connected components. (ii) Every cluster has at most five outgoing edges.

Moreover, the cd-tree reveals interesting connections between c-planarity and planarity with constraints on the order of edges around vertices. On one hand, this gives rise to a bunch of new open problems related to c-planarity, on the other hand it provides a new perspective on previous results.
Original languageEnglish
Pages (from-to)306-315
JournalTheoretical Computer Science
Volume609
DOIs
Publication statusPublished - 4 Jan 2016
Externally publishedYes

Keywords

  • Graph drawing
  • Clustered planarity
  • Constrained planar embedding
  • Characterization
  • Algorithms

Cite this