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.

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
ID Code:156

Repository Staff Only: item control page

References

K. A. Baker, P. C. Fishburn, and F. S. Roberts (1971) Partial orders of dimension 2, Networks (2), 11-28.

G. di Battista, W.-P. Liu and I. Rival (1990) Bipartite graphs, upward drawings, and planarity, Inform. Proc. Letters 36, 317-322.

G. di Battista and R. Tamassia (1988) Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science 61, 175-198.

J. Czyzowicz. A. Pelc and I. Rival (1990) Planar ordered sets of width two, Math. Slovaca 40 (4), 375-388.

K. Ewacha, W. Li, and I. Rival (1991) Order, genus and diagram invariance, ORDER 8, 107-113.

S. Foldes, I. Rival and J. Urrutia, Light sources, obstructions, and spherical orders, Discrete Math. 102, 13-23.

M. R. Garey and D. S. Johnson (1979) Computers and Intractability : A Guide to the Theory of NP-completeness. Freeman.

A. Garg and R. Tamassia (1995) On the computational complexity of upward and rectilinear planarity testing, Lecture Notes in Computer Science (894) (eds. R. Tamassia and I. G. Tollis), pp. 286-297.

A. Garg and R. Tamassia (1995) Upward planarity testing, ORDER (12(2)).

S. Mehdi Hashemi and I. Rival (1994) Upward drawings to fit surfaces, in Orders, Algorithms, and Applications (ORDAL'94) (eds. V. Bouchitté and M. Morvan), Lecture Notes in Computer Science 831, Springer pp. 53-58.

J. Hopcroft and R. E. Tarjan (1974) Efficient planarity testing, J. Ass. Comp. Mach. 21 (4), 549-568.

M. D. Hutton and A. Lubiw (1991) Upward planar drawing of single source acyclic digraphs, Proc. 2nd A.C.M./S.I.A.M. Symposium Discrete Appl. Math., pp. 203-211.

D. Kelly (1987) Fundamentals of planar ordered sets, Discrete Math. 63, 197-216.

D. Kelly and I. Rival (1975) Planar lattices, Canad. J. Math. 27, 636-665.

A. Kisielewicz and I. Rival (1993) Every triangle-free planar graph has a planar upward drawing, ORDER 10, 1-16.

A. Lempel, S. Even and I. Cederbaum (1967) An algorithm for planarity testing of graphs, in Theory of Graphs, International Symposium, Rome (1966) (P. Rosenstiehl ed.) Gordon and Breach, pp. 215-232.

C. R. Platt (1976) Planar lattices and planar graphs, J. Comb. Th. Ser. B 21, 30-39.

K. Reuter and I. Rival (1991) Genus of orders and lattices, in Graph-Theoretic Concepts in Computer Science (R. Möhring ed.), Lect. Notes Comp. Sci. 484, pp. 260-275.

I. Rival (1993) Reading, drawing, and order, in Algebras and Orders (I. G. Rosenberg ed.), Kluwer.

C. Thomassen (1989) Planar acyclic oriented graphs, ORDER 5, 349-361.