2019/11/16 by Ruo-Wei Hung, Hung, Ruo-Wei, Fatemeh Keshavarz-Kohjerdi +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1911.08558
21 pages, 27 figures. arXiv admin note: substantial text overlap with arXiv:1908.07447, arXiv:1904.02581
arxiv created 2019/11/16 · arxiv updated 2019/11/21
In this paper, we continue the study of the Hamiltonian and longest (s, t)-paths of supergrid graphs. The Hamiltonian (s, t)-path of a graph is a Hamiltonian path between any two given vertices s and t in the graph, and the longest (s, t)-path is a simple path with the maximum number of vertices from s to t in the graph. A graph holds Hamiltonian connected property if it contains a Hamiltonian (s, t)-path. These two problems are well-known NP-complete for general supergrid graphs. An O-shaped supergrid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we first prove the Hamiltonian connectivity of O-shaped supergrid graphs except few conditions. We then show that the longest (s, t)-path of an O-shaped supergrid graph can be computed in linear time. The Hamiltonian and longest (s, t)-paths of O-shaped supergrid graphs can be applied to compute the minimum trace of computerized embroidery machine and 3D printer when a hollow object is printed.