2019/04/04 by Fatemeh Keshavarz-Kohjerdi, Keshavarz-Kohjerdi, Fatemeh, Ruo-Wei Hung +1 · 2 citations
Computer Science · Mathematics · #05C38 #05C85 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C38 #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1904.02581
A preliminary version of this paper has appeared in: The International MultiConference of Engineers and Computer Scientists 2018 (IMECS 2018), Hong Kong, vol. I, 2018, pp. 117-122
arxiv created 2019/05/06 · arxiv updated 2019/05/07
Supergrid graphs contain grid graphs and triangular grid graphs as their subgraphs. The Hamiltonian cycle and path problems for general supergrid graphs were known to be NP-complete. A graph is called Hamiltonian if it contains a Hamiltonian cycle, and is said to be Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices in it. In this paper, we first prove that every L-shaped supergrid graph always contains a Hamiltonian cycle except one trivial condition. We then verify the Hamiltonian connectivity of L-shaped supergrid graphs except few conditions. The Hamiltonicity and Hamiltonian connectivity of L-shaped supergrid graphs can be applied to compute the minimum trace of computerized embroidery machine and 3D printer when a L-like object is printed. Finally, we present a linear-time algorithm to compute the longest (s, t)-path of L-shaped supergrid graph given two distinct vertices s and t.