Skip to main content
SpringerLink
Log in

Drawing planar graphs using the canonical ordering

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:

  • Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n−4)×(n−2) grid, wheren is the number of vertices.

  • Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.

  • Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.

  • Every triconnected planar graphG admits a planar polyline grid drawing on a (2n−6)×(3n−9) grid with minimum angle larger than 2/d radians and at most 5n−15 bends, withd the maximum degree.

These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bhasker, J., and S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph,Algorithmica 3 (1988), 147–178.

    Google Scholar 

  2. Biedl, T., and G. Kant, A better heuristic for planar orthogonal drawings, inProc. 2nd European Symp. on Algorithms (ESA '94), Lecture Notes in Computer Science, Vol. 855, Springer-Verlag, Berlin, 1994, pp. 24–36.

    Google Scholar 

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

    Google Scholar 

  4. Chiba, N., T. Nishizeki, S. Abe, and T. Ozawa, A linear algorithm for embedding planar graphs using PQ-trees,J. Comput. System Sci. 30 (1985), 54–76.

    Google Scholar 

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

    Google Scholar 

  6. Chrobak, M., and G. Kant, Convex Grid Drawings of 3-Connected Planar Graphs, Tech. Rep. RUU-CS-93-45, Dept. of Computer Science, Utrecht University, 1993.

  7. Chrobak, M., and T. H. Payne, A Linear Time Algorithm for Drawing Planar Graphs on the Grid, Tech. Rep. UCR-CS-90-2, Dept. of Mathematics and Computer Science, University of California at Riverside, 1990.

    Google Scholar 

  8. Cohen, R. F., G. Di Battista, R. Tamassia, I. G. Tollis, and P. Bertolazzi, A framework for dynamic graph drawing, inProc. 8th Annual ACM Symp. on Computational Geometry, 1992, pp. 261–270.

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

    Google Scholar 

  10. Di Battista, G., G. Liotta, and F. Vargiu, Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs, inProc. Workshop on Algorithms and Data Structures (WADS '93), Lecture Notes in Computer Science, Vol. 709, Springer-Verlag, 1993, Berlin, pp. 151–162.

    Google Scholar 

  11. Di Battista, G., and R. Tamassia, Incremental planarity testing, inProc. 30th Annual IEEE Symp. on Foundations of Computer Science (FOCS '89), 1989, pp. 436–441.

  12. Di Battista, G., R. Tamassia, and I. G. Tollis, Area requirement and symmetry display in drawing graphs,Discrete Comput. Geom. 7 (1992), 381–401.

    Google Scholar 

  13. Di Battista, G., and L. Vismara, Angles of planar triangular graphs, extended abstract inProc. 25th Annual ACM Symp. on Theory of Computing, 1993, pp. 431–437.

  14. Even, S., and G. Granot, Rectilinear Planar Drawings with Few Bends in Each Edge, Manuscript, Faculty of Computer Science, The Technion, Haifa, 1993.

    Google Scholar 

  15. Even, S., and R. E. Tarjan, Computing anst-numbering,Theoret. Comp. Sci. 2 (1976), 436–441.

    Google Scholar 

  16. Fáry, I., On straight line representations of planar graphs,Acta Sci. Math. Szeged,11 (1948), 229–233.

    Google Scholar 

  17. Formann, M., T. Hagerup, J. Haralambides, M. Kaufmann, F. T. Leighton, A. Simvonis, E. Welzl, and G. Woeginger, Drawing graphs in the plane with high resolution,SIAM J. Comput. 22 (1993), 1035–1052.

    Google Scholar 

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

    Google Scholar 

  19. Garg, A., and R. Tamassia, On the computational complexity of upward and rectilinear planarity testing, inProc. Graph Drawing '94, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1994, to appear.

    Google Scholar 

  20. Garg, A., and R. Tamassia, Planar drawings and angular resolution: algorithms and bounds, inProc. 2nd European Symp. on Algorithms (ESA '94), Lecture Notes in Computer Science, Vol. 855, Springer-Verlag, Berlin, 1994, pp. 12–23.

    Google Scholar 

  21. Haandel, F. van, Straight Line Embeddings on the Grid, M.Sc. Thesis, No. INF/SCR-91-19, Dept. of Computer Science, Utrecht University, 1991.

  22. He, X., On finding the rectangular duals of planar triangulated graphs,SIAM J. Comput., 1993, to appear.

  23. He, X., and M.-Y. Kao, Parallel construction of canonical ordering and convex drawing of triconnected planar graphs, inProc. 4th Symp. on Algorithms and Computation (ISAAC '93), Lecture Notes in Computer Science, Vol. 762, 1993, pp. 303–312.

    Google Scholar 

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

    Google Scholar 

  25. Hopcroft, J., and R. E. Tarjan, Efficient planarity testing,J. Assoc. Comput. Mach. 21 (1974), 549–568.

    Google Scholar 

  26. Jayakumar, R., K. Thulasiraman, and M. N. S. Swamy, Planar embedding: linear-time algorithms for vertex placement and edge ordering,IEEE Trans. Circuits and Systems 35 (1988), 334–344.

    Google Scholar 

  27. Kant, G., Hexagonal grid drawings, inProc. 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '92), Lecture Notes in Computer Science, Vol. 657, Springer-Verlag, Berlin, 1992, 263–276.

    Google Scholar 

  28. Kant, G., Algorithms for Drawing Planar Graphs, Ph.D. thesis, Dept. of Computer Science, Utrecht University, 1993.

  29. Kant, G., The planar triconnectivity augmentation problem, submitted toTheoret. Comput. Sci., 1993.

  30. Kant, G., A more compact visibility representation, inProc. 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '93), Lecture Notes in Computer Science, Vol. 790, Springer-Verlag, Berlin, 1994, 411–424.

    Google Scholar 

  31. Kant, G., and X. He, Two algorithms for finding rectangular duals of planar graphs, inProc. 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '93), Lecture Notes in Computer Science, Vol. 790, Springer-Verlag, 1994, pp. 396–410.

  32. Lempel, A., S. Even, and I. Cederbaum, An algorithm for planarity testing of graphs,Theory of Graphs, International Symp., Rome, 1966, pp. 215–232.

  33. Liu, Y., P. Marchioro, and R. Petreschi, At most single-bend embeddings of cubic graphs,Appl. Math., 1994, to appear.

  34. Liu, Y., P. Marchioro, R. Petreschi, and B. Simeone, Theoretical Results on at Most 1-Bend Embeddability of Graphs, Tech. Rep., Dept. of Statistics, University “La Sapienza” Roma, 1990.

  35. Lin, Y.-L., and S. S. Skiena, Complexity Aspects of Visibility Graphs, Rep. 92-08, Dept. of Computer Science, State University of New York, Stony Brook, NY, 1992.

    Google Scholar 

  36. Malitz, S., and A. Papakostas, On the angular resolution of planar graphs,SIAM J. Discrete Math. 7 (1994), 172–183.

    Google Scholar 

  37. Nummenmaa, J., Constructing compact rectilinear planar layouts using canonical representation of planar graphs,Theoret. Comput. Sci. 99 (1992), 213–230.

    Google Scholar 

  38. Rosenstiehl, P., and R. E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs,Discrete Comput. Geom. 1 (1986), 343–353.

    Google Scholar 

  39. Schnyder, W., Embedding planar graphs on the grid, inProc. 1st Annual ACM-SIAM Symp. on Discrete Algebra (SODA '90), 1990, pp. 138–147.

  40. Stein, S. K., Convex maps,Proc. Amer. Math. Soc. 2 (1951), 464–466.

    Google Scholar 

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

    Google Scholar 

  42. Tamassia, R., On embedding a graph in the grid with the minimum number of bends,SIAM J. Comput. 16 (1987), 421–444.

    Google Scholar 

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

    Google Scholar 

  44. Tamassia, R., and I. G. Tollis, A unified approach to visibility representations of planar graphs,Discrete and Comput. Geom. 1 (1986), 321–341.

    Google Scholar 

  45. Tamassia, R., I. G. Tollis, and J. S. Vitter, Lower bounds for planar orthogonal drawings of graphs,Inform. Process. Lett. 39 (1991), 35–40.

    Google Scholar 

  46. Thomassen, C., Planarity and duality of finite and infinite planar graphs,J. Combin. Theory Ser. B 29 (1980), 244–271.

    Google Scholar 

  47. Tutte, W. T., Convex representations of graphs,Proc. London Math. Soc. 10 (1960), 302–320.

    Google Scholar 

  48. Tutte, W. T., How to draw a graph,Proc. London Math. Soc. 13 (1963), 743–768.

    Google Scholar 

  49. Wagner, K., Bemerkungen zum vierfarbenproblem,Jahresber. Deutsch. Math.-Verein. 46 (1936), 26–32.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands

    G. Kant

Authors
  1. G. Kant
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by G. Di Battista and R. Tamassia.

This work was supported by the ESPRIT Basic Research Actions program of the EC under Contract No. 7141 (project ALCOM II). An extended abstract of this paper was presented at the 33rd Annual IEEE Symposium on the Foundations of Computer Science, Pittsburgh, 1992. This is a revised version of Technical Report RUU-CS-92-33.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kant, G. Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996). https://doi.org/10.1007/BF02086606

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02086606

Key words

Search

Navigation