The complexity of upward drawings on spheres (Q1272953)

Usually, an ordered set is identified with its geometric representation, called its upward drawing, where the elements of the ordered set \(P\) are drawn on a surface, traditionally a plane, as disjoint small circles, arranged in such a way that for \(a, b\in P\), the circle corresponding to \(a\) is higher than the circle corresponding to \(b\) whenever \(a>b\) and an arc, monotonic with respect to a fixed direction, is drawn to join them just if \(a\) covers \(b\). An ordered set is said to be planar if it has an upward drawing in the plane in which no arcs cross, although they may meet at a vertex with which they are incident. A recent result due to \textit{A. Garg} and \textit{R. Tamassia} [Order 12, 109-133 (1995; Zbl 0836.68081)] states that upward planarity testing is NP-complete. The main result of this paper is that the decision problem whether an ordered set has an upward drawing on a sphere is NP-complete. The proof involves the investigation of the surface topology of ordered sets highlighting especially their saddle points. A simpler proof of Garg and Tamassia's theorem, based on an exact cover by 3-sets is given. Finally, three open problems are stated.