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 , pp. 277-286(Official URL: http://dx.doi.org/10.1007/BFb0021811).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/BFb0021811
Classifications: P Styles > P.840 Upward
Z Theory > Z.750 Topology
P Styles > P.060 3D
URI: http://gdea.informatik.uni-koeln.de/id/eprint/156

Actions (login required)

View Item View Item