“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 453
School of Mathematics
  Title:   Digraph embedding
  Author(s):  S. M. Hashemi
  Status:   Published
  Journal: Discrete Math.
  Vol.:  233
  Year:  2001
  Pages:   321-328
  Supported by:  IPM
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.

Download TeX format
back to top
scroll left or right