Geodesic
Switch-Regular Upward Planarity Testing of Directed Trees
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010) , Tome 15 (2011) no. 5, pp. 587-629.

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

Upward planar drawings of digraphs are crossing free drawings where all edges flow in the upward direction. The problem of deciding whether a digraph admits an upward planar drawing is called the upward planarity testing problem, and it has been widely studied in the literature. In this paper we investigate a new upward planarity testing problem, that is, deciding whether a digraph admits an upward planar drawing having some special topological properties: such a drawing is called switch-regular. Switch-regular upward planar drawings have practical algorithmic impacts in several graph drawing applications. We provide characterizations for the class of directed trees that admit a switch-regular upward planar drawing. Based on these characterizations we describe an optimal linear-time testing and embedding algorithm.
DOI : 10.7155/jgaa.00241
Keywords: Upward Planarity Testing, Switch-regularity 
@article{JGAA_2011_15_5_a2,
     author = {Carla Binucci and Emilio Di Giacomo and Walter Didimo and Aimal Rextin},
     title = {Switch-Regular {Upward} {Planarity} {Testing} of {Directed} {Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {587--629},
     publisher = {mathdoc},
     volume = {15},
     number = {5},
     year = {2011},
     doi = {10.7155/jgaa.00241},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00241/}
}
TY  - JOUR
AU  - Carla Binucci
AU  - Emilio Di Giacomo
AU  - Walter Didimo
AU  - Aimal Rextin
TI  - Switch-Regular Upward Planarity Testing of Directed Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 587
EP  - 629
VL  - 15
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00241/
DO  - 10.7155/jgaa.00241
LA  - en
ID  - JGAA_2011_15_5_a2
ER  - 
%0 Journal Article
%A Carla Binucci
%A Emilio Di Giacomo
%A Walter Didimo
%A Aimal Rextin
%T Switch-Regular Upward Planarity Testing of Directed Trees
%J Journal of Graph Algorithms and Applications
%D 2011
%P 587-629
%V 15
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00241/
%R 10.7155/jgaa.00241
%G en
%F JGAA_2011_15_5_a2
Carla Binucci; Emilio Di Giacomo; Walter Didimo; Aimal Rextin. Switch-Regular Upward Planarity Testing of Directed Trees. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010)
					, Tome 15 (2011) no. 5, pp. 587-629. doi : 10.7155/jgaa.00241. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00241/

Cité par Sources :