Area requirement and symmetry display of planar upward drawings

1. P. Bertolazzi and G. Di Battista, On upward drawing testing of triconnected digraphs,Proceedings of the ACM Symposium on Computational Geometry, 1991, pp. 272–280.

2. N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa, A linear algorithm for embedding planar graphs using PQ-trees,Journal of Computer and System Sciences 30 (1985), 54–76.

   Article  MathSciNet  MATH  Google Scholar 

3. N. Chiba, K. Onoguchi, and T. Nishizeki, Drawing planar graphs nicely,Acta Informatica 22 (1985), 187–201.

   Article  MathSciNet  MATH  Google Scholar 

4. M. Chrobak, A linear-time algorithm for drawing a planar graph on a grid, Manuscript, University of California, Riverside, 1988.

   Google Scholar 

5. G. Di Battista, W.-P. Liu, and I. Rival, Bipartite graphs, upward drawings, and planarity,Information Processing Letters 36 (1990), 317–322.

   Article  MathSciNet  MATH  Google Scholar 

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

   Article  MathSciNet  MATH  Google Scholar 

7. D. Dolev, F. T. Leighton, and H. Trickey, Planar embedding of planar graphs, inAdvances in Computing Research, vol. 2, F. P. Preparata, ed., JAI Press, Greenwich, CT, 1984, pp. 147–161.

   Google Scholar 

8. P. Eades, A heuristic for graph drawing,Congressus Numerantium 42 (1984), 149–160.

   MathSciNet  Google Scholar 

9. P. Eades and R. Tamassia, Algorithms for automatic graph drawing: An annotated bibliography, Technical Report CS-89-09, Dept. of Computer Science, Brown University, 1989.

10. P. Eades and R. Tamassia, Algorithms for automatic graph drawing: An annotated bibliography,Networks (1992), to appear.

11. I. Fary, On straight lines representation of planar graphs,Acta Scientiarum Mathematicarum (Szeged) 11 (1948), 229–233.

    MathSciNet  MATH  Google Scholar 

12. H. de Fraysseix, J. Pach, and R. Pollack, Small sets supporting Fary embeddings of planar graphs,Proceedings of the 20th ACM Symposium on Theory of Computing, 1988, pp. 426–433.

13. H. de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid,Combinatorica 10 (1990), 41–51.

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

15. L. J. Guibas and F. F. Yao, On translating a set of rectangles, inAdvances in Computing Research, vol. 1, F. P. Preparata, ed., JAI Press, Greenwich, CT, 1983, pp. 61–77.

    Google Scholar 

16. J. Hopcroft and R. E. Tarjan, Efficient planarity testing,Journal of the Association for Computing Machinery 21 (1974), 549–568.

    Article  MathSciNet  MATH  Google Scholar 

17. M. Y. Hsueh and D. O. Pederson, Computer-aided layout of LSI circuit building-blocks,Proceedings of the IEEE International Symposium on Circuits and Systems, 1979, pp. 474–477.

18. M. D. Hutton and A. Lubiw, Upward planar drawing of single source acyclic digraphs,Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 203–211.

19. T. Kameda, On the vector representation of the reachability in planar directed graphs,Information Processing Letters 3 (1975), 75–77.

    Article  MathSciNet  MATH  Google Scholar 

20. D. Kelly, Fundamentals of planar ordered sets,Discrete Mathematics 63 (1987), 197–216.

    Article  MathSciNet  MATH  Google Scholar 

21. D. Kelly and I. Rival, Planar lattices,Canadian Journal of Mathematics 27 (1975), 636–665.

    Article  MathSciNet  MATH  Google Scholar 

22. D. Kelly and W. T. Trotter, Dimension theory for ordered sets, inOrdered Sets, I. Rival, ed., Reidel, Dordrecht, 1982, pp. 171–211.

    Chapter  Google Scholar 

23. A. Lempel, S. Even, and I. Cederbaum, An algorithm for planarity testing of graphs,Theory of Graphs (Proc. International Symposium), Gordon and Breach, New York, 1967, pp. 215–232.

    Google Scholar 

24. R. Lipton, S. North, and J. Sandberg, A method for drawing graphs,Proceedings of the ACM Symposium on Computational Geometry, 1985, pp. 153–160.

25. J. Manning, Computational complexity of geometric symmetry detection in graphs, Technical Report CSC-90-1, Dept. of Computer Science, University of Missouri, Rolla, 1990.

    Google Scholar 

26. J. Manning and M. J. Atallah, Fast detection and display of symmetry in outerplanar graphs, Technical Report CSD-TR-606, Dept. of Computer Sciences, Purdue University, West Lafayette, 1986.

    Google Scholar 

27. J. Manning and M. J. Atallah, Fast detection and display of symmetry in trees,Congressus Numerantium 64 (1988), 159–169.

    MathSciNet  Google Scholar 

28. C. Platt, Planar lattices and planar graphs,Journal of Combinatorial Theory, Series B 21 (1976), 30–39.

    Article  MathSciNet  MATH  Google Scholar 

29. R. Read, New methods for drawing a planar graph given the cyclic order of the edges at Each Vertex,Congressus Numerantium 56 (1987), 31–44.

    MathSciNet  Google Scholar 

30. E. Reingold and J. Tilford, Tidier drawing of trees,IEEE Transactions on Software Engineering 7 (1981), 223–228.

    Article  Google Scholar 

31. I. Rival, Graphical data structures for ordered sets, inAlgorithms and Order, I. Rival, ed., Kluwer, Boston, 1989, pp. 3–31.

    Chapter  Google Scholar 

32. I. Rival and J. Urrutia, Representing orders by translating convex figures in the plane,Order 4 (1988), 319–339.

    Article  MathSciNet  MATH  Google Scholar 

33. P. Rosenstiehl and R. E. Tarjan, Rectilinear planar layouts of planar graphs and bipolar orientations,Discrete & Computational Geometry 1 (1986), 343–353.

    Article  MathSciNet  MATH  Google Scholar 

34. W. Schnyder, Embedding planar graphs on the grid,Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138–148.

35. S. K. Stein, Convex maps,Proceedings of the American Mathematical Society 2 (1951), 464–466.

    Article  MathSciNet  MATH  Google Scholar 

36. E. Steinitz and H. Rademacher,Vorlesung uber die Theorie der Polyeder, Springer-Verlag, Berlin, 1934.

    Google Scholar 

37. J. A. Storer, On minimal node-cost planar embeddings,Networks 14 (1984), 181–212.

    Article  MathSciNet  MATH  Google Scholar 

38. K. J. Supowit and E. M. Reingold, The complexity of drawing trees nicely,Acta Informatica 18 (1983), 377–392.

    Article  MathSciNet  MATH  Google Scholar 

39. R. Tamassia, On embedding a graph in the grid with the minimum number of bends,SIAM Journal on Computing 16 (1987), 421–444.

    Article  MathSciNet  MATH  Google Scholar 

40. R. Tamassia, G. Di Battista, and C. Batini, Automatic graph drawing and readability of diagrams,IEEE Transactions on Systems, Man and Cybernetics 18 (1988), 61–79.

    Article  Google Scholar 

41. R. Tamassia and F. P. Preparata, Dynamic maintenance of planar digraphs, with applications,Algorithmica 5 (1990), 509–527.

    Article  MathSciNet  MATH  Google Scholar 

42. R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs,Discrete & Computational Geometry 1 (1986), 321–341.

    Article  MathSciNet  MATH  Google Scholar 

43. R. Tamassia and I. G. Tollis, Planar grid embedding in linear time,IEEE Transactions on Circuits and Systems 36 (1989), 1230–1234.

    Article  MathSciNet  Google Scholar 

44. C. Thomassen, Planar acyclic oriented graphs,Order 5 (1989), 349–361.

    Article  MathSciNet  MATH  Google Scholar 

45. W. T. Tutte, How to draw a graph,Proceedings of the London Mathematical Society 3 (1963), 743–768.

    Article  MathSciNet  Google Scholar 

46. K. Wagner, Bemerkungen zum Vierfarbenproblem,Jahresbericht der Deutschen Mathematiker-Vereinigung 46 (1936), 26–32.

    Google Scholar 

47. D. Woods, Drawing planar graphs, Ph.D. dissertation (Technical Report STAN-CS-82-943), Computer Science Dept., Stanford University, 1982.

Download references