Upward Three-Dimensional Grid Drawings of Graphs | Order Skip to main content
Springer Nature Link
Log in

Upward Three-Dimensional Grid Drawings of Graphs

  • Published:
Order Aims and scope Submit manuscript

Abstract

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. Our first main result is that every \(n\)-vertex graph with bounded degeneracy has a three-dimensional grid drawing with \(\mathcal{O}\left({n^{3/2}}\right)\) volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the \(\textsf{z}\)-direction. We prove that every dag has an upward three-dimensional grid drawing with \(\mathcal{O}\left({n^3}\right)\) volume, which is tight for the complete dag. The previous best upper bound was \(\mathcal{O}\left({n^4}\right)\). Our main result concerning upward drawings is that every \(c\)-colourable dag (\(c\) constant) has an upward three-dimensional grid drawing with \(\mathcal{O}\left({n^2}\right)\) volume. This result matches the bound in the undirected case, and improves the best known bound from \(\mathcal{O}\left({n^3}\right)\) for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Albertson, M.O., Chappell, G.G., Kierstead, H.A., Kündgen, A., Ramamurthi, R.: Coloring with no 2-colored \({P}_4\)'s. Electron. J. Combin. 11 #R26 (2004)

  2. Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132–169 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bose, P., Czyzowicz, J., Morin, P., Wood, D.R.: The maximum number of edges in a three-dimensional grid-drawing. J. Graph Algorithms Appl. 8(1), 21–26 (2004)

    MATH  MathSciNet  Google Scholar 

  4. Calamoneri, T., Sterbini, A.: 3D straight-line grid drawing of 4-colorable graphs. Inf. Process. Lett. 63(2), 97–102 (1997)

    Article  MathSciNet  Google Scholar 

  5. Cohen, R.F., Eades, P., Lin, T., Ruskey, F.: Three-dimensional graph drawing. Algorithmica 17(2), 199–208 (1996)

    Article  MathSciNet  Google Scholar 

  6. Devillers, O., Everett, H., Lazard, S., Pentcheva, M., Wismath, S.: Drawing \(K_{\,n}\) in three dimensions with one bend per edge. In: Healy, P., Nikolov, N.S. (eds.) Proc. 13th International Symp. on Graph Drawing (GD '05). Lecture Notes in Comput. Sci., vol. 3843, pp. 83–88. Springer, Berlin Heidelberg New York (2006)

  7. Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs, NJ (1999)

    MATH  Google Scholar 

  8. Di Giacomo, E., Liotta, G., Meijer, H.: Computing straight-line 3D grid drawings of graphs in linear volume. Comput. Geom. 32(1), 26–58 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  9. Di Giacomo, E., Liotta, G., Meijer, H., Wismath, S.K.: Volume requirements of 3D upward drawings. In: Healy, P., Nikolov, N.S. (eds) Proc. 13th International Symp. on Graph Drawing (GD '05). Lecture Notes in Comput. Sci., vol. 3843, pp. 101–110. Springer, Berlin Heidelberg New York (2006)

  10. Di Giacomo, E., Meijer, H.: Track drawings of graphs with constant queue number. In: Liotta, G. (ed.) Proc. 11th International Symp. on Graph Drawing (GD '03). Lecture Notes in Comput. Sci., vol. 2912, pp. 214–225. Springer, Berlin Heidelberg New York (2004)

  11. Dujmović, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width. SIAM J. Comput. 34(3), 553–579 (2005)

    Article  MathSciNet  Google Scholar 

  12. Dujmović, V., Pór, A., Wood, D.R.: Track layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 497–522 (2004)

    MathSciNet  Google Scholar 

  13. Dujmović, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 339–358 (2004)

    MathSciNet  Google Scholar 

  14. Dujmović, V., Wood, D.R.: Three-dimensional grid drawings with sub-quadratic volume. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs. Contemporary Mathematics, vol. 342, pp. 55–66. Amer. Math. Soc. (2004)

  15. Dujmović, V., Wood, D.R.: Stacks, queues and tracks: layouts of graph subdivisions. Discrete Math. Theor. Comput. Sci. 7, 155–202 (2005)

    MathSciNet  Google Scholar 

  16. Edwards, K.: The harmonious chromatic number and the achromatic number. In: Surveys in combinatorics. London Math. Soc. Lecture Note Ser., vol. 241, pp. 13–47. Cambridge University Press, Cambridge, UK (1997)

    Google Scholar 

  17. Edwards, K., McDiarmid, C.: New upper bounds on harmonious colorings. J. Graph Theory 18(3), 257–267 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  18. Felsner, S., Liotta, G., Wismath, S.K.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl. 7(4), 363–398 (2003)

    MATH  MathSciNet  Google Scholar 

  19. Fertin, G., Raspaud, A., Reed, B.: On star coloring of graphs. J. Graph Theory 47(3), 163–182 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  20. Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  21. Harary, F., Schwenk, A.: A new crossing number for bipartite graphs. Util. Math. 1, 203–209 (1972)

    MATH  MathSciNet  Google Scholar 

  22. Hasunuma, T.: Laying out iterated line digraphs using queues. In: Liotta, G. (ed.) Proc. 11th International Symp. on Graph Drawing (GD '03). Lecture Notes in Comput. Sci., vol. 2912, pp. 202–213. Springer, Berlin Heidelberg New York (2004)

  23. Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5(3), 398–412 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  24. Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs. II. SIAM J. Comput. 28(5), 1588–1626 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  25. Heath, L.S., Pemmaraju, S.V., Trenk, A.N.: Stack and queue layouts of directed acyclic graphs. II. SIAM J. Comput. 28(4), 1510–1539 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  26. Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927–958 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  27. Hutton, M.D., Lubiw, A.: Upward planar drawing of single-source acyclic digraphs. SIAM J. Comput. 25(2), 291–311 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  28. Kaufmann, M., Wagner, D. (eds.): Drawing Graphs: Methods and Models. Lecture Notes in Comput. Sci., vol. 2025. Springer, Berlin Heidelberg New York (2001)

    Google Scholar 

  29. Leighton, F.T., Rosenberg, A.L.: Three-dimensional circuit layouts. SIAM J. Comput. 15(3), 793–813 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  30. Morin, P., Wood, D.R.: Three-dimensional 1-bend graph drawings. J. Graph Algorithms Appl. 8(3), 357–366 (2004)

    MATH  MathSciNet  Google Scholar 

  31. Nešetřil, J., de Mendez, P.O.: Colorings and homomorphisms of minor closed classes. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry, The Goodman-Pollack Festschrift. Algorithms and Combinatorics, vol. 25, pp. 651–664. Springer, Berlin Heidelberg New York (2003)

    Google Scholar 

  32. Pach, J., Thiele, T., Tóth, G.: Three-dimensional grid drawings of graphs. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in discrete and computational geometry. Contemporary Mathematics, vol. 223, pp. 251–255. Amer. Math. Soc. (1999)

  33. Pór, A., Wood, D.R.: No-3-in-line-3D. In: Pach, J. (ed.) Proc. 12th International Symp. on Graph Drawing (GD '04). Lecture Notes in Comput. Sci., vol. 3383, pp. 395–402. Springer, Berlin Heidelberg New York (2004). To appear in Algorithmica

  34. Poranen, T.: A new algorithm for drawing series-parallel digraphs in 3D. Tech. Rep. A-2000-16, Dept. of Computer and Information Sciences, University of Tampere, Finland (2000)

  35. Ware, C., Franck, G.: Viewing a graph in a virtual reality display is three times as good as a 2D diagram. In: Ambler, A.L., Kimura, T.D. (eds.) Proc. IEEE Symp. Visual Languages (VL '94), pp. 182–183. IEEE (1994)

  36. Ware, C., Franck, G.: Evaluating stereo and motion cues for visualizing information nets in three dimensions. ACM Trans. Graphics 15(2), 121–140 (1996)

    Article  Google Scholar 

  37. Ware, C., Hui, D., Franck, G.: Visualizing object oriented software in three dimensions. In: Proc. IBM Centre for Advanced Studies Conf. (CASCON '93), pp. 1–11 (1993)

  38. Wood, D.R.: Drawing a graph in a hypercube (2004). http://arxiv.org/math/0509455

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, Carleton University, Ottawa, Canada

    Vida Dujmović

  2. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain

    David R. Wood

Authors
  1. Vida Dujmović
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David R. Wood
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vida Dujmović.

Additional information

Research of Vida Dujmovi\(\grave c\) is supported by NSERC. Research of David Wood is supported by the Government of Spain grant MEC SB2003-0270 and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dujmović, V., Wood, D.R. Upward Three-Dimensional Grid Drawings of Graphs. Order 23, 1–20 (2006). https://doi.org/10.1007/s11083-006-9028-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11083-006-9028-y

Mathematics Subject Classification (1991)

Key words

Search

Navigation