%0 Journal Article
%T Linear Sphericity Testing of 3-Connected Single Source Digraphs
%J Bulletin of the Iranian Mathematical Society
%I Iranian Mathematical Society (IMS)
%Z 1017-060X
%A Dolati, A.
%D 2011
%\ 03/15/2011
%V 37
%N No. 3
%P 291-304
%! Linear Sphericity Testing of 3-Connected Single Source Digraphs
%K Embedding
%K upward embedding
%K sphericity
%K single
source digraph
%R
%X It has been proved that sphericity testing for digraphs is an
NP-complete problem. Here, we
investigate sphericity of 3-connected single source digraphs. We
provide a new combinatorial characterization of sphericity and give
a linear time algorithm for sphericity testing. Our algorithm tests
whether a 3-connected single source digraph with $n$ vertices is
spherical in $O(n)$ time.
%U http://bims.iranjournals.ir/article_366_32f7b095391488c7c2d848a209f52492.pdf