Geodesic
Planarity of Overlapping Clusterings Including Unions of Two Partitions
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1057-1089.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We consider clustered planarity with overlapping clusters as introduced by Didimo et al. (Didimo, Giordano, Liotta, JGAA, 2008). It can be deduced from a proof in Athenstädt et al. (J. C. Athenstädt, T. Hartmann, and M. Nöllenburg, GD 2014) 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. 
@article{JGAA_2017_21_6_a4,
     author = {Jan Christoph Athenst\"adt and Sabine Cornelsen},
     title = {Planarity of {Overlapping} {Clusterings} {Including} {Unions} of {Two} {Partitions}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {1057--1089},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2017},
     doi = {10.7155/jgaa.00450},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00450/}
}
TY  - JOUR
AU  - Jan Christoph Athenstädt
AU  - Sabine Cornelsen
TI  - Planarity of Overlapping Clusterings Including Unions of Two Partitions
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 1057
EP  - 1089
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00450/
DO  - 10.7155/jgaa.00450
LA  - en
ID  - JGAA_2017_21_6_a4
ER  - 
%0 Journal Article
%A Jan Christoph Athenstädt
%A Sabine Cornelsen
%T Planarity of Overlapping Clusterings Including Unions of Two Partitions
%J Journal of Graph Algorithms and Applications
%D 2017
%P 1057-1089
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00450/
%R 10.7155/jgaa.00450
%G en
%F JGAA_2017_21_6_a4
Jan Christoph Athenstädt; Sabine Cornelsen. Planarity of Overlapping Clusterings Including Unions of Two Partitions. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1057-1089. doi : 10.7155/jgaa.00450. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00450/

Cité par Sources :