Linear sphericity testing of 3-connected single source digraphs (Q1758790)

Graph embeddings and their generalization on surfaces have many applications such as VLSI layout, and graphical representations of a poset. In this paper author focus on the spherical diagraph i.e., diagraph that has an upward embedding on the round sphere. \textit{S.M. Hashemi}, \textit{I. Rival} and \textit{A. Kisielewicz} [``The complexity of upward drawings on spheres,'' Order 14, No.\,4, 327--363 (1998; Zbl 0913.06001)] proved that sphericity testing for digraphs (i.e., the test to set if D is a spherical digraph) is an NP-complete problem. Here, author investigates sphericity of 3-connected single source digraphs. He provides a new combinatorial characterization of sphericity and he gives a linear time algorithm for sphericity testing. His algorithm tests whether a 3-connected single source digraph with \(n\) vertices is spherical in \(O(n)\) time.