On the sphericity testing of single source digraphs Original Research Article

A digraph image is called spherical, if it has an upward embedding on the round sphere which is an embedding of image on the round sphere so that all edges are monotonic arcs and all point to a fixed direction, say to the north pole. It is easy to see that [S.M. Hashemi, Digraph embedding, Discrete Math. 233 (2001) 321–328] for upward embedding, plane and sphere are not equivalent, which is in contrast with the fact that they are equivalent for undirected graphs. On the other hand, it has been proved that sphericity testing for digraphs is an NP-complete problem []. In this work we study sphericity testing of the single source digraphs. In particular, we shall present a polynomial time algorithm for sphericity testing of three connected single source digraphs.