### Abstract

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 language | English |
---|---|

Pages (from-to) | 306-315 |

Journal | Theoretical Computer Science |

Volume | 609 |

DOIs | |

Publication status | Published - 4 Jan 2016 |

Externally published | Yes |

### Keywords

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

### Cite this

}

*Theoretical Computer Science*, vol. 609, pp. 306-315. https://doi.org/10.1016/j.tcs.2015.10.011

**A new perspective on clustered planarity as a combinatorial embedding problem.** / Blaesius, T.; Rutter, I.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - A new perspective on clustered planarity as a combinatorial embedding problem

AU - Blaesius, T.

AU - Rutter, I.

PY - 2016/1/4

Y1 - 2016/1/4

N2 - 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.

AB - 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.

KW - Graph drawing

KW - Clustered planarity

KW - Constrained planar embedding

KW - Characterization

KW - Algorithms

U2 - 10.1016/j.tcs.2015.10.011

DO - 10.1016/j.tcs.2015.10.011

M3 - Article

VL - 609

SP - 306

EP - 315

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -