The Hamiltonicity, Hamiltonian Connectivity, and Longest (s, t)-path of L-shaped Supergrid Graphs

Fatemeh Keshavarz-Kohjerdi | Ruo-Wei Hung

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137730
Date :  2020/08/15
Publish in :    IAENG International Journal of Computer Science

Link :  http://www.iaeng.org/IJCS/issues_v47/issue_3/index.html
Keywords :Hamiltonicity, Hamiltonian connectivity, longest (s, t)-path, solid supergrid graphs, L-shaped supergrid graphs, computer embroidery machines, 3D printers

Abstract :

---

Supergrid (or called strong grid) graphs contain grid graphs and triangular grid graphs as their subgraphs. The Hamiltonian (s, t)-path of a graph is a Hamiltonian path between any two distinct 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 is called Hamiltonian if it contains a Hamiltonian cycle, and is said to be Hamiltonian connected if there exists a Hamiltonian (s, t)-path in it. These problems are known to be NP-complete for general supergrid graphs. As far as we know, their complexities are still unknown for solid supergrid graphs which are supergrid graphs without any hole. In this paper, we will study these problems on L-shaped supergrid graphs which form a subclass of solid supergrid graphs. First, we prove L-shaped supergrid graphs to be Hamiltonian 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)-paths of Lshaped supergrid graphs. This study can be regarded as the first attempt for solving the Hamiltonian and longest (s, t)-path problems on solid supergrid graphs