Revista de la
Unión Matemática Argentina
Hamiltonicity of rectangular grid graphs (meshes) with an L‑shaped hole
Movahedeh Rouhani-Marchoobeh and Fatemeh Keshavarz-Kohjerdi

Volume 68, no. 2 (2025), pp. 611–625    

Published online (final version): October 8, 2025

https://doi.org/10.33044/revuma.4432

Download PDF

Abstract

Finding the Hamiltonian cycles in graphs is a well-known problem. Although the Hamiltonicity of grid graphs has been studied in the literature, there are few results on Hamiltonicity of grid graphs with holes. In this paper, we study the Hamiltonicity of rectangular grid graphs (meshes) with an L-shaped hole, and give a linear-time algorithm. The holes in meshes correspond to the faulty nodes.

References

  1. F. Afrati, The Hamilton circuit problem on grids, RAIRO Inform. Théor. Appl. 28 no. 6 (1994), 567–582.  DOI  MR  Zbl
  2. E. M. Arkin, S. P. Fekete, K. Islam, H. Meijer, J. S. B. Mitchell, Y. Núñez Rodríguez, V. Polishchuk, D. Rappaport, and H. Xiao, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, Comput. Geom. 42 no. 6-7 (2009), 582–605.  DOI  MR  Zbl
  3. A. Asgharian Sardroud and A. Bagheri, Embedding cycles and paths on solid grid graphs, J. Supercomput. 73 no. 4 (2017), 1322–1336.  DOI
  4. J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier, New York, 1976.  MR  Zbl
  5. S. D. Chen, H. Shen, and R. Topor, An efficient algorithm for constructing Hamiltonian paths in meshes, Parallel Comput. 28 no. 9 (2002), 1293–1305.  DOI  MR  Zbl
  6. V. S. Gordon, Y. L. Orlovich, and F. Werner, Hamiltonian properties of triangular grid graphs, Discrete Math. 308 no. 24 (2008), 6166–6188.  DOI  MR  Zbl
  7. K. Hou and J. Lynch, The computational complexity of finding Hamiltonian cycles in grid graphs of semiregular tessellations, in Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG 2018), University of Manitoba, Winnipeg, 2018, pp. 114–128. Available at https://web.archive.org/web/20250731033946/https://cccg.ca/proceedings/2018/proceedings.pdf.
  8. R.-W. Hung, Hamiltonian cycles in linear-convex supergrid graphs, Discrete Appl. Math. 211 (2016), 99–112.  DOI  MR  Zbl
  9. R.-W. Hung, C.-C. Yao, and S.-J. Chan, The Hamiltonian properties of supergrid graphs, Theoret. Comput. Sci. 602 (2015), 132–148.  DOI  MR  Zbl
  10. C. Icking, T. Kamphans, R. Klein, and E. Langetepe, Exploring simple grid polygons, in Computing and combinatorics, Lecture Notes in Comput. Sci. 3595, Springer, Berlin, 2005, pp. 524–533.  DOI  MR  Zbl
  11. K. Islam, H. Meijer, Y. Núñez Rodríguez, D. Rappaport, and H. Xiao, Hamilton circuits in hexagonal grid graphs, in Proceedings of the 19th Canadian Conference of Computational Geometry (CCCG), 2007. Available at https://web.archive.org/web/20250802140616/https://cccg.ca/proceedings/2007/04a2.pdf.
  12. A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput. 11 no. 4 (1982), 676–686.  DOI  MR  Zbl
  13. F. Keshavarz-Kohjerdi, Off-line exploration of rectangular cellular environments with a rectangular obstacle, Optim. Methods Softw. 37 no. 5 (2022), 1805–1819.  DOI  MR  Zbl
  14. F. Keshavarz-Kohjerdi and A. Bagheri, Hamiltonian paths in $L$-shaped grid graphs, Theoret. Comput. Sci. 621 (2016), 37–56.  DOI  MR  Zbl
  15. F. Keshavarz-Kohjerdi and A. Bagheri, Linear-time algorithms for finding Hamiltonian and longest $(s,t)$-paths in $C$-shaped grid graphs, Discrete Optim. 35 (2020), article no. 100554.  DOI  MR  Zbl
  16. F. Keshavarz-Kohjerdi and A. Bagheri, Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time, Appl. Math. Comput. 436 (2023), article no. 127513.  DOI  MR  Zbl
  17. F. Keshavarz-Kohjerdi and A. Bagheri, The Hamiltonicity and Hamiltonian-connectivity of solid supergrid graphs, Bull. Malays. Math. Sci. Soc. 46 no. 3 (2023), article no. 110.  DOI  MR  Zbl
  18. F. Keshavarz-Kohjerdi and A. Bagheri, A linear-time algorithm for finding Hamiltonian cycles in rectangular grid graphs with two rectangular holes, Optim. Methods Softw. 38 no. 3 (2023), 591–625.  DOI  MR  Zbl
  19. F. Keshavarz-Kohjerdi and A. Bagheri, Hamiltonian $(s,t)$-paths in solid supergrid graphs, Comput. Appl. Math. 43 no. 3 (2024), article no. 110.  DOI  MR  Zbl
  20. R. I. Nishat and S. Whitesides, Reconfiguring Hamiltonian cycles in L-shaped grid graphs, in Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci. 11789, Springer, Cham, 2019, pp. 325–337.  DOI  MR  Zbl
  21. J. R. Reay and T. Zamfirescu, Hamiltonian cycles in T-graphs, Discrete Comput. Geom. 24 no. 2-3 (2000), 497–502.  DOI  MR  Zbl
  22. A. N. M. Salman, Contributions to graph theory, Ph.D. thesis, University of Twente, 2005. Available at https://research.utwente.nl/en/publications/contributions-to-graph-theory-2.
  23. A. N. M. Salman, E. T. Baskoro, and H. J. Broersma, A note concerning Hamilton cycles in some classes of grid graphs, J. Math. Fundam. Sci. 35 no. 1 (2003), 65–70.
  24. C. Umans and W. Lenhart, Hamiltonian cycles in solid grid graphs, in Proceedings. 38th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, California, 1997, pp. 496–505.  DOI
  25. C. Zamfirescu and T. Zamfirescu, Hamiltonian properties of grid graphs, SIAM J. Discrete Math. 5 no. 4 (1992), 564–570.  DOI  MR  Zbl