Digraph embedding Original Research Article

An upward embedding of a digraph (directed graph) on the plane or a surface is an embedding of its underlying graph so that all directed edges are monotonic and point to a fixed direction. Such embedding in some literatures is called upward drawing without crossing of edges. For a given digraph G to decide whether it has an upward embedding on the plane is known as an NP-Complete problem (cf. [6,4]). In this paper we study the problem of upward embedding of digraphs on the round sphere. We shall present a characterization of all spherical digraphs.