zbMATH — the first resource for mathematics

Hamiltonian cycles in linear-convex supergrid graphs. (English) Zbl 1348.05117
Summary: A supergrid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional supergrid. The supergrid graphs contain grid graphs and triangular grid graphs as subgraphs. The Hamiltonian cycle problem for grid and triangular grid graphs was known to be NP-complete. Recently, we have proved the Hamiltonian cycle problem on supergrid graphs to be NP-complete. The Hamiltonian cycle problem on supergrid graphs can be applied to control the stitching trace of computerized sewing machines. In this paper, we will study the Hamiltonian cycle property of linear-convex supergrid graphs which form a subclass of supergrid graphs. A connected graph is called \(k\)-connected if there are \(k\) vertex-disjoint paths between every pair of vertices, and is called locally connected if the neighbors of each vertex in it form a connected subgraph. In this paper, we first show that any 2-connected, linear-convex supergrid graph is locally connected. We then give constructive proofs to show that any 2-connected, linear-convex supergrid graph contains a Hamiltonian cycle. Based on the constructive proofs, we finally present a linear-time algorithm to construct a Hamiltonian cycle of a 2-connected, linear-convex supergrid graph.

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
Full Text: DOI arXiv
[1] Ascheuer, N., Hamiltonian path problems in the on-line optimization of flexible manufacturing systems, technique report TR 96-3, (1996), Konrad-Zuse-Zentrum für Informationstechnik Berlin
[2] Bermond, J. C., Hamiltonian graphs, (Beinke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, (1978), Academic Press New York) · Zbl 0329.05113
[3] Bertossi, A. A.; Bonuccelli, M. A., Hamiltonian circuits in interval graph generalizations, Inform. Process. Lett., 23, 195-200, (1986) · Zbl 0627.68056
[4] Bondy, J. A.; Murty, U. S.R., Graph theory, (2008), Springer New York · Zbl 1134.05001
[5] Bouchemakh, I.; Zemir, M., On the broadcast independence number of grid graph, Graphs Comb., 30, 83-100, (2014) · Zbl 1295.05173
[6] Chen, S. D.; Shen, H.; Topor, R., An efficient algorithm for constructing Hamiltonian paths in meshes, Parallel Comput., 28, 1293-1305, (2002) · Zbl 0999.68253
[7] Damaschke, P., The Hamiltonian circuit problem for circle graphs is NP-complete, Inform. Process. Lett., 32, 1-2, (1989) · Zbl 0681.68062
[8] Dettlaff, M.; Lemańskaa, M.; Yero, I. G., Bondage number of grid graphs, Discrete Appl. Math., 167, 94-99, (2014) · Zbl 1284.05195
[9] Faudree, R. J.; Flandrin, E.; Ryjáček, Z., Claw-free graphs—a survey, Discrete Math., 164, 87-147, (1997) · Zbl 0879.05043
[10] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[11] Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57, (2004), Elsevier) · Zbl 1050.05002
[12] Gordon, V. S.; Orlovich, Y. L.; Werner, F., Hamiltonin properties of triangular grid graphs, Discrete Math., 308, 6166-6188, (2008) · Zbl 1158.05040
[13] Gravier, S., Total domination number of grid graphs, Discrete Appl. Math., 121, 119-128, (2002) · Zbl 0995.05109
[14] Grebinski, V.; Kucherov, G., Reconstructing a Hamiltonian cycle by querying the graph: application to DNA physical mapping, Discrete Appl. Math., 88, 147-165, (1998) · Zbl 0936.68107
[15] Gulak, P.; Kailath, T., Locally connected VLSI architectures for the viterbi algorithm, IEEE J. Sel. Areas Commun., 6, 3, 527-537, (1988)
[16] Hendry, G. R.T., Extending cycles in graphs, Discrete Math., 85, 59-72, (1990) · Zbl 0714.05038
[17] Hu, F. T.; Lu, Y.; Xu, J. M., The total bondage number of grid graphs, Discrete Appl. Math., 160, 2408-2418, (2012) · Zbl 1252.05163
[18] Hung, R. W.; Yao, C. C.; Chan, S. J., The Hamiltonian properties of supergrid graphs, Theoret. Comput. Sci., 602, 132-148, (2015) · Zbl 1330.05093
[19] Islam, K.; Meijer, H.; Núũez, Y.; Rappaport, D.; Xiao, H., Hamiltonian cycles in hexagonal grid graphs, (Proceedings of the 19th Canadian Conference on Computational Geometry, CCCG’97, (2007)), 85-88
[20] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 4, 676-686, (1982) · Zbl 0506.05043
[21] Johnson, D. S., The NP-complete column: an ongoing guide, J. Algorithms, 6, 434-451, (1985) · Zbl 0608.68032
[22] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in some classes of grid graphs, J. Appl. Math., 2012, (2012), article no. 475087 · Zbl 1245.05081
[23] Keshavarz-Kohjerdi, F.; Bagheri, A.; Asgharian-Sardroud, A., A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math., 160, 210-217, (2012) · Zbl 1237.05115
[24] Krishnamoorthy, M. S., An NP-hard problem in bipartite graphs, SIGACT News, 7, 26, (1976)
[25] Lenhart, W.; Umans, C., Hamiltonian cycles in solid grid graphs, (Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS’97, (1997)), 496-505
[26] Marx, D., Eulerian disjoint paths problem in grid graphs is NP-complete, Discrete Appl. Math., 143, 336-341, (2004) · Zbl 1053.05078
[27] Menke, B.; Zamfirescu, T.; Zamfirescu, C., Intersections of longest cycles in grid graphs, J. Graph Theory, 25, 37-52, (1997) · Zbl 0874.05032
[28] Muthammai, S.; Vidhya, P., Total complementary tree domination in grid graphs, Internat. J. Math. Soft Comput., 3, 107-114, (2013)
[29] O’Callaghan, J. F., Computing the perceptual boundaries of dot patterns, Comput. Graphics Image Process., 3, 141-162, (1974)
[30] Preperata, F. P.; Shamos, M. I., Computational geometry: an introduction, (1985), Springer New York
[31] Reay, J. R.; Zamfirescu, T., Hamiltonian cycles in T-graphs, Discrete Comput. Geom., 24, 497-502, (2000) · Zbl 0953.05040
[32] Salman, A. N.M., Contributions to graph theory, (2005), University of Twente, (Ph.D. thesis)
[33] Toussaint, G. T., Pattern recognition and geometrical complexity, (Proceedings of the 5th International Conference on Pattern Recognition, Miami Beach, (1980)), 1324-1347
[34] Zamfirescu, C.; Zamfirescu, T., Hamiltonian properties of grid graphs, SIAM J. Discrete Math., 5, 564-570, (1992) · Zbl 0770.05073
[35] Zhang, W. Q.; Liu, Y. J., Approximating the longest paths in grid graphs, Theoret. Comput. Sci., 412, 5340-5350, (2011) · Zbl 1222.68089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.