Record number :

947303

Title of article :

On the sphericity testing of single source digraphs Original Research Article

Author/Authors :

Ardeshir Dolati، نويسنده , , S. Mehdi Hashemi، نويسنده ,

Issue Information :

روزنامه با شماره پیاپی سال 2008

Pages :

7

From page :

2175

To page :

2181

Abstract :

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.

Keywords :

Upward embedding , Planarity , Single source digraph , Embedding , Sphericity , Upward planarity

Journal title :

Discrete Mathematics

Serial Year :

2008

Link To Document :