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 :
بازگشت