Upward planarity testing

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

Bertolazzi, P., Cohen, R. F., Di Battista, G., Tamassia, R., and Tollis, I. G. (1994) How to draw a series-parallel digraph,Internat. J. Comput. Geom. Appl. 4, 385?402.

Bertolazzi, P. and Di Battista, G. (1991) On upward drawing testing of triconnected digraphs, inProc. 7th Annu. ACM Sympos. Comput. Geom, pp. 272?280.

Bertolazzi, P., Di Battista, G, Liotta, G., and Mannino, C. (1994) Upward drawings of triconnected digraphs,Algorithmica 12, 476?497.

Bertolazzi, P., Di Battista, G., Mannino, C., and Tamassia, R. (1993) Optimal upward planarity testing of single-source digraphs, in1st Annual European Symposium on Algorithms (ESA '93), Vol. 726 ofLecture Notes in Computer Science, Springer-Verlag, pp. 37?48.

Birkhoff, G. (1967)Lattice Theory, American Mathematical Society, Providence, RI.

Bondy, J. A. and Murty, U. S. R. (1976)Graph Theory with Applications, North-Holland, New York, NY.

Booth, K. and Lueker, G. (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms,J. Comput. Syst. Sci. 13, 335?379.

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. (1990)Introduction to Algorithms, The MIT Press, Cambridge, Mass.

de Fraysseix, H. and Rosenstiehl, P. (1982) A depth-first-search characterization of planarity,Annals of Dicrete Mathematics 13, 75?80.

Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. (1994) Algorithms for drawing graphs: an annotated bibliography,Comput. Geom. Theory Appl. 4, 235?282.

Di Battista, G., Liu, W. P., and Rival, I. (1990) Bipartite graphs, upward drawings, and planarity,Inform. Process. Lett. 36, 317?322.

Di Battista, G. and Tamassia, R. (1988) Algorithms for plane representations of acyclic digraphs,Theoret. Comput. Sci. 61, 175?198.

Di Battista, G. and Tamassia, R. (1990) On-line graph algorithms with SPQR-trees, inAutomata, Languages and Programming (Proc. 17th ICALP), Vol. 442 ofLecture Notes in Computer Science, pp. 598?611.

Di Battista, G., Tamassia, R., and Tollis, I. G. (1992) Area requirement and symmetry display of planar upward drawings,Discrete Comput. Geom. 7, 381?401.

Garey, M. R. and Johnson, D. S. (1979)Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, NY.

Garg, A. and Tamassia, R. (1995) On the computational complexity of upward and rectilinear planarity testing, in R. Tamassia and I. G. Tollis (eds),Graph Drawing (Proc. GD '94), Vol. 894 ofLecture Notes in Computer Science, Springer-Verlag, pp. 286?297.

Hopcroft, J. and Tarjan, R. E. (1973) Dividing a graph into triconnected components,SIAM J. Comput. 2, 135?158.

Hopcroft, J. and Tarjan, R. E. (1974) Efficient planarity testing,J. ACM 21(4), 549?568.

Hutton, M. D. and Lubiw, A. (1991) Upward planar drawing of single source acyclic digraphs, inProc. 2nd ACM-SIAM Sympos. Discrete Algorithms, pp. 203?211.

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

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

Lempel, A., Even, S., and Cederbaum, I. (1967) An algorithm for planarity testing of graphs, inTheory of Graphs: Internat. Symposium (Rome 1966), Gordon and Breach, New York, pp. 215?232.

Papakostas, A. (1995) Upward planarity testing of outerplanar dags, in R. Tamassia and I. G. Tollis (eds),Graph Drawing (Proc. GD '94), Vol. 894 ofLecture Notes in Computer Science, Springer-Verlag, pp. 298?306.

Platt, C. (1976) Planar lattices and planar graphs,J. Combin. Theory Ser. B 21, 30?39.

Rival, I. (1993) Reading, drawing, and order, in I. G. Rosenberg and G. Sabidussi (eds),Algebras and Orders, Kluwer Academic Publishers, pp. 359?404.

Thomassen, C. (1989) Planar acyclic oriented graphs,Order 5(4), 349?361.