Upward Drawings on Planes and Spheres
Hashemi, S. Mehdi and Kisielewicz, Andrzej and Rival, Ivan (1996) Upward Drawings on Planes and Spheres. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 277-286 (Official URL: http://dx.doi.org/10.1007/BFb0021811).
Full text not available from this repository.
Although there is a linear time algorithm to decide whether an ordered set has an upward drawing on a surface topologically equivalent to a sphere, we shall prove that the decision problem whether an ordered set has an upward drawing on a sphere itself is NP-complete. To this end we explore the surface topology of ordered sets highlighting especially the role of their saddle points.
Repository Staff Only: item control page