@article { author = {Dolati, A.}, title = {Linear Sphericity Testing of 3-Connected Single Source Digraphs}, journal = {Bulletin of the Iranian Mathematical Society}, volume = {37}, number = {No. 3}, pages = {291-304}, year = {2011}, publisher = {Iranian Mathematical Society (IMS)}, issn = {1017-060X}, eissn = {1735-8515}, doi = {}, abstract = {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.}, keywords = {Embedding,upward embedding,sphericity,single source digraph}, url = {http://bims.iranjournals.ir/article_366.html}, eprint = {http://bims.iranjournals.ir/article_366_32f7b095391488c7c2d848a209f52492.pdf} }