On the sphericity testing of single source digraphs

A digraph D=(V,A)D=(V,A) is called spherical, if it has an upward embedding on the round sphere which is an embedding of DD 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 [ S.M. Hashemi, A. Kisielewicz, I. Rival, The complexity of upward drawings on spheres, Order 14 (1998) 327–363]. 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.