Abstract
Acyclic digraphs, such as the covering digraphs of ordered sets, are usually drawn upward, i.e., with the edges monotonically increasing in the vertical direction. A digraph is upward planar if it admits an upward planar drawing. In this survey paper, we overview the literature on the problem of upward planarity testing. We present several characterizations of upward planarity and describe upward planarity testing algorithms for special classes of digraphs, such as embedded digraphs and single-source digraphs. We also sketch the proof of NP-completeness of upward planarity testing.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
Author information
Authors and Affiliations
Additional information
Communicated by I. Rival
Research supported in part by the National Science Foundation under grant CCR-9423847.
Rights and permissions
About this article
Cite this article
Garg, A., Tamassia, R. Upward planarity testing. Order 12, 109–133 (1995). https://doi.org/10.1007/BF01108622
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01108622