KOPS - The Institutional Repository of the University of Konstanz
# Planarity of Overlapping Clusterings Including Unions of Two Partitions

Type of Publication: | Journal article |

Publication status: | Published |

Author: | Athenstädt, Jan C.; Cornelsen, Sabine |

Year of publication: | 2017 |

Published in: | Journal of Graph Algorithms and Applications ; 21 (2017), 6. - pp. 1057-1089. - eISSN 1526-1719 |

DOI (citable link): | https://dx.doi.org/10.7155/jgaa.00450 |

Summary: |
We consider clustered planarity with overlapping clusters as introduced by Didimo et al. [14]. It can be deduced from a proof in Athenstädt et al. [2] that the problem is NP-complete, even if restricted to instances where the underlying graph is 2-connected, the set of clusters is the union of two partitions and each cluster contains at most two connected components while their complements contain at most three connected components.
In this paper, we show that clustered planarity with overlapping clusters can be solved in polynomial time if each cluster induces a connected subgraph. It can be solved in linear time if the set of clusters is the union of two partitions of the vertex set such that, for each cluster, both the cluster and its complement induce connected subgraphs. |

Subject (DDC): | 004 Computer Science |

Bibliography of Konstanz: | Yes |

Refereed: | Yes |

Files | Size | Format | View |
---|---|---|---|

There are no files associated with this item. |

ATHENSTÄDT, Jan C., Sabine CORNELSEN, 2017. Planarity of Overlapping Clusterings Including Unions of Two Partitions. In: Journal of Graph Algorithms and Applications. 21(6), pp. 1057-1089. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00450

@article{Athenstadt2017Plana-44791, title={Planarity of Overlapping Clusterings Including Unions of Two Partitions}, year={2017}, doi={10.7155/jgaa.00450}, number={6}, volume={21}, journal={Journal of Graph Algorithms and Applications}, pages={1057--1089}, author={Athenstädt, Jan C. and Cornelsen, Sabine} }