Geodesic
Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Fifteenth International Symposium on Graph Drawing, GD 2007 , Tome 13 (2009) no. 3, pp. 379-422.

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

We present several polynomial-time algorithms for c-planarity testing for cluster hierarchy C containing clusters of size at most three. The main result is an O(|C|3 + n)-time algorithm for clusters of size at most three on a cycle. The result is then generalized to a special class of Eulerian graphs, namely graphs obtained from a 3-connected planar graph of fixed size k by multiplying and then subdividing edges. An O(3k ·k ·n3)-time algorithm is presented. We further give an O(|C|2 + n)-time algorithm for general 3-connected planar graphs. 
@article{JGAA_2009_13_3_a4,
     author = {Eva Jel{\'\i}nkov\'a and Jan K\'ara and Jan Kratochv{\'\i}l and Martin Pergel and Ond\v{r}ej Such\'y and Tom\'a\v{s} Vyskocil},
     title = {Clustered {Planarity:} {Small} {Clusters} in {Cycles} and {Eulerian} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {379--422},
     publisher = {mathdoc},
     volume = {13},
     number = {3},
     year = {2009},
     doi = {10.7155/jgaa.00192},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00192/}
}
TY  - JOUR
AU  - Eva Jelínková
AU  - Jan Kára
AU  - Jan Kratochvíl
AU  - Martin Pergel
AU  - Ondřej Suchý
AU  - Tomáš Vyskocil
TI  - Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2009
SP  - 379
EP  - 422
VL  - 13
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00192/
DO  - 10.7155/jgaa.00192
LA  - en
ID  - JGAA_2009_13_3_a4
ER  - 
%0 Journal Article
%A Eva Jelínková
%A Jan Kára
%A Jan Kratochvíl
%A Martin Pergel
%A Ondřej Suchý
%A Tomáš Vyskocil
%T Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs
%J Journal of Graph Algorithms and Applications
%D 2009
%P 379-422
%V 13
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00192/
%R 10.7155/jgaa.00192
%G en
%F JGAA_2009_13_3_a4
Eva Jelínková; Jan Kára; Jan Kratochvíl; Martin Pergel; Ondřej Suchý; Tomáš Vyskocil. Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Fifteenth International Symposium on Graph Drawing, GD 2007
					, Tome 13 (2009) no. 3, pp. 379-422. doi : 10.7155/jgaa.00192. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00192/

Cité par Sources :