On the sphericity testing of single source digraphs (Q2483398)

The paper first presents a combinatorial characterization of spherical digraphs in terms of critical points, where a digraph is said to be spherical if it has an upward embedding on the round sphere which is an embedding of the digraph on the round sphere so that all edges are monotonic arcs and all point to a fixed direction, and then discusses a polynomial time algorithm to determine whether a single source digraph with a given embedding on the plane has a similar upward embedding on the sphere. In other words, it is shown that there is a polynomial time algorithm for sphericity testing of three connected single source digraphs.