[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Unit-length Rectangular Drawings of Graphs

  • Conference paper
  • First Online:
Graph Drawing and Network Visualization (GD 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13764))

Included in the following conference series:

Abstract

A rectangular drawing of a planar graph G is a planar drawing of G in which vertices are mapped to grid points, edges are mapped to horizontal and vertical straight-line segments, and faces are drawn as rectangles. Sometimes this latter constraint is relaxed for the outer face. In this paper, we study rectangular drawings in which the edges have unit length. We show a complexity dichotomy for the problem of deciding the existence of a unit-length rectangular drawing, depending on whether the outer face must also be drawn as a rectangle or not. Specifically, we prove that the problem is \(\textsf{NP}\)-complete for biconnected graphs when the drawing of the outer face is not required to be a rectangle, even if the sought drawing must respect a given planar embedding, whereas it is polynomial-time solvable, both in the fixed and the variable embedding settings, if the outer face is required to be drawn as a rectangle.

This research was partially supported by MIUR Project “AHeAD” under PRIN 20174LF3T8, and by H2020-MSCA-RISE project 734922 – “CONNECT”.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 55.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 69.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Note that in some literature the term “grid graph” denotes an “induced” graph, i.e., there is an edge between any two vertices at distance one. See, for example, [31].

References

  1. Abel, Z., Demaine, E.D., Demaine, M.L., Eisenstat, S., Lynch, J., Schardl, T.B.: Who needs crossings? Hardness of plane graph rigidity. In: Fekete, S.P., Lubiw, A. (eds.) 32nd International Symposium on Computational Geometry (SoCG 2016). LIPIcs, vol. 51, pp. 3:1–3:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPIcs.SoCG.2016.3

  2. Alegría, C., Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: Planar straight-line realizations of 2-trees with prescribed edge lengths. In: Purchase, H.C., Rutter, I. (eds.) GD 2021. LNCS, vol. 12868, pp. 166–183. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92931-2_12

    Chapter  Google Scholar 

  3. Alegría, C., Da Lozzo, G., Di Battista, G., Frati, F., Grosso, F., Patrignani, M.: Unit-length rectangular drawings of graphs. CoRR abs/2208.14142 (2022). https://arxiv.org/abs/2208.14142

  4. Angelini, P., et al.: Anchored drawings of planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 404–415. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45803-7_34

    Chapter  Google Scholar 

  5. Angelini, P., Da Lozzo, G., Frati, F., Lubiw, A., Patrignani, M., Roselli, V.: Optimal morphs of convex drawings. In: Arge, L., Pach, J. (eds.) 31st International Symposium on Computational Geometry, SoCG 2015, 22–25 June 2015, Eindhoven, The Netherlands. LIPIcs, vol. 34, pp. 126–140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015). https://doi.org/10.4230/LIPIcs.SOCG.2015.126

  6. Asgharian Sardroud, A., Bagheri, A.: Embedding cycles and paths on solid grid graphs. J. Supercomputing 73(4), 1322–1336 (2016). https://doi.org/10.1007/s11227-016-1811-y

    Article  Google Scholar 

  7. Beck, M., Storandt, S.: Puzzling grid embeddings. In: Blelloch, G.E., Finocchi, I. (eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020, Salt Lake City, UT, USA, 5–6 January 2020, pp. 94–105. SIAM (2020)

    Google Scholar 

  8. de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(03), 187–205 (2012). https://doi.org/10.1142/S0218195912500045

    Article  MathSciNet  Google Scholar 

  9. Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inf. Process. Lett. 25(4), 263–267 (1987). https://doi.org/10.1016/0020-0190(87)90173-6

    Article  Google Scholar 

  10. Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998). https://doi.org/10.1016/S0925-7721(97)00026-6

    Article  MathSciNet  Google Scholar 

  11. Borradaile, G., Klein, P.N., Mozes, S., Nussbaum, Y., Wulff-Nilsen, C.: Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM J. Comput. 46(4), 1280–1303 (2017). https://doi.org/10.1137/15M1042929

    Article  MathSciNet  Google Scholar 

  12. Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Algorithms Appl. 11(1), 259–276 (2007). https://doi.org/10.7155/jgaa.00145

    Article  MathSciNet  Google Scholar 

  13. Chang, Y., Yen, H.: On bend-minimized orthogonal drawings of planar 3-graphs. In: 33rd International Symposium on Computational Geometry, SoCG 2017, 4–7 July 2017, Brisbane, Australia, pp. 29:1–29:15 (2017). https://doi.org/10.4230/LIPIcs.SoCG.2017.29

  14. Cornelsen, S., Karrenbauer, A.: Accelerated bend minimization. J. Graph Algorithms Appl. 16(3), 635–650 (2012). https://doi.org/10.7155/jgaa.00265

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  16. Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764–1811 (1998). https://doi.org/10.1137/S0097539794262847

    Article  MathSciNet  Google Scholar 

  17. Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996). https://doi.org/10.1007/BF01961541

    Article  MathSciNet  Google Scholar 

  18. Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956–997 (1996)

    Article  MathSciNet  Google Scholar 

  19. Di Battista, G., Tamassia, R., Vismara, L.: Incremental convex planarity testing. Inf. Comput. 169(1), 94–126 (2001). https://doi.org/10.1006/inco.2001.3031

    Article  MathSciNet  Google Scholar 

  20. Didimo, W., Kaufmann, M., Liotta, G., Ortali, G.: Rectilinear planarity testing of plane series-parallel graphs in linear time. In: GD 2020. LNCS, vol. 12590, pp. 436–449. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-68766-3_34

    Chapter  Google Scholar 

  21. Didimo, W., Liotta, G., Ortali, G., Patrignani, M.: Optimal orthogonal drawings of planar 3-graphs in linear time. In: Chawla, S. (ed.) Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 806–825. ACM-SIAM (2020). https://doi.org/10.1137/1.9781611975994.49

  22. Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Disc. Appl. Math. 28(2), 111–134 (1990). https://doi.org/10.1016/0166-218X(90)90110-X

    Article  MathSciNet  Google Scholar 

  23. Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 213–248. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-0110-0_12

  24. Frati, F.: Planar rectilinear drawings of outerplanar graphs in linear time. In: Auber, D., Valtr, P. (eds.) GD 2020. LNCS, vol. 12590, pp. 423–435. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-68766-3_33

    Chapter  Google Scholar 

  25. Garg, A., Liotta, G.: Almost bend-optimal planar orthogonal drawings of biconnected degree-3 planar graphs in quadratic time. In: Kratochvíyl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 38–48. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-46648-7_4

    Chapter  Google Scholar 

  26. Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001). https://doi.org/10.1137/S0097539794277123

    Article  MathSciNet  Google Scholar 

  27. Gregori, A.: Unit-length embedding of binary trees on a square grid. Inf. Process. Lett. 31(4), 167–173 (1989). https://doi.org/10.1016/0020-0190(89)90118-X

    Article  MathSciNet  Google Scholar 

  28. Gupta, S., Sa’ar, G., Zehavi, M.: Grid recognition: classical and parameterized computational perspectives (2021). https://doi.org/10.48550/ARXIV.2106.16180

  29. Hasan, M.M., Rahman, M.S.: No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract). In: Du, D.-Z., Duan, Z., Tian, C. (eds.) COCOON 2019. LNCS, vol. 11653, pp. 254–265. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26176-4_21

    Chapter  Google Scholar 

  30. Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973). https://doi.org/10.1145/362248.362272

    Article  Google Scholar 

  31. Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676–686 (1982). https://doi.org/10.1137/0211056

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  33. Liu, Y., Morgana, A., Simeone, B.: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Appl. Math. 81(1–3), 69–91 (1998). https://doi.org/10.1016/S0166-218X(97)00076-0

    Article  MathSciNet  Google Scholar 

  34. Miura, K., Haga, H., Nishizeki, T.: Inner rectangular drawings of plane graphs. Int. J. Comput. Geom. Appl. 16(2–3), 249–270 (2006). https://doi.org/10.1142/S0218195906002026

    Article  MathSciNet  Google Scholar 

  35. Nishizeki, T., Rahman, M.S.: Planar Graph Drawing, Lecture Notes Series on Computing, vol. 12. World Scientific (2004). https://doi.org/10.1142/5648

  36. Nishizeki, T., Rahman, M.S.: Rectangular drawing algorithms. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 317–348. Chapman and Hall/CRC (2013)

    Google Scholar 

  37. Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of series-parallel graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 409–420. Springer, Heidelberg (2006). https://doi.org/10.1007/11618058_37

    Chapter  Google Scholar 

  38. Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE Trans. 88-D(1), 23–30 (2005)

    Google Scholar 

  39. Rahman, M.S., Nakano, S., Nishizeki, T.: Rectangular grid drawings of plane graphs. Comput. Geom. 10(3), 203–220 (1998). https://doi.org/10.1016/S0925-7721(98)00003-0

    Article  MathSciNet  Google Scholar 

  40. Rahman, M.S., Nakano, S., Nishizeki, T.: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Algorithms Appl. 3(4), 31–62 (1999). http://www.cs.brown.edu/publications/jgaa/accepted/99/SaidurNakanoNishizeki99.3.4.pdf

  41. Rahman, M.S., Nishizeki, T.: Bend-minimum orthogonal drawings of plane 3-graphs. In: Graph-Theoretic Concepts in Computer Science, 28th International Workshop, WG 2002, Cesky Krumlov, Czech Republic, 13–15 June 2002, Revised Papers, pp. 367–378 (2002). https://doi.org/10.1007/3-540-36379-3_32

  42. Rahman, M.S., Nishizeki, T., Ghosh, S.: Rectangular drawings of planar graphs. J. Algorithms 50(1), 62–78 (2004). https://doi.org/10.1016/S0196-6774(03)00126-3

    Article  MathSciNet  Google Scholar 

  43. Rahman, M.S., Nishizeki, T., Naznin, M.: Orthogonal drawings of plane graphs without bends. J. Graph Algorithms Appl. 7(4), 335–362 (2003). http://jgaa.info/accepted/2003/Rahman+2003.7.4.pdf

  44. Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461–482. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-0110-0_24

  45. Storer, J.A.: The node cost measure for embedding graphs on the planar grid (extended abstract). In: Miller, R.E., Ginsburg, S., Burkhard, W.A., Lipton, R.J. (eds.) Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 28–30 April 1980, Los Angeles, California, USA, pp. 201–210. ACM (1980). https://doi.org/10.1145/800141.804667

  46. Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987). https://doi.org/10.1137/0216030

    Article  MathSciNet  Google Scholar 

  47. Thomassen, C.: Plane representations of graphs. In: Bondy, J., Murty, U. (eds.) Progress in Graph Theory, pp. 43–69. Academic Press, Toronto, Orlando (1987)

    Google Scholar 

  48. Ungar, P.: On Diagrams Representing Maps. J. London Math. Soc. s1–28(3), 336–342 (1953). https://doi.org/10.1112/jlms/s1-28.3.336

  49. Vijayan, G., Wigderson, A.: Rectilinear graphs and their embeddings. SIAM J. Comput. 14(2), 355–372 (1985)

    Article  MathSciNet  Google Scholar 

  50. Zhou, X., Nishizeki, T.: Orthogonal drawings of series-parallel graphs with minimum bends. SIAM J. Discrete Math. 22(4), 1570–1604 (2008). https://doi.org/10.1137/060667621

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering, Roma Tre University, Rome, Italy

    Carlos Alegría, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso & Maurizio Patrignani

Authors
  1. Carlos Alegría
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giordano Da Lozzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giuseppe Di Battista
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Fabrizio Frati
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Fabrizio Grosso
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Maurizio Patrignani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giordano Da Lozzo .

Editor information

Editors and Affiliations

  1. John Cabot University, Rome, Italy

    Patrizio Angelini

  2. Kiel University, Kiel, Germany

    Reinhard von Hanxleden

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Alegría, C., Da Lozzo, G., Di Battista, G., Frati, F., Grosso, F., Patrignani, M. (2023). Unit-length Rectangular Drawings of Graphs. In: Angelini, P., von Hanxleden, R. (eds) Graph Drawing and Network Visualization. GD 2022. Lecture Notes in Computer Science, vol 13764. Springer, Cham. https://doi.org/10.1007/978-3-031-22203-0_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-22203-0_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-22202-3

  • Online ISBN: 978-3-031-22203-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation