# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time  
[PERSON]  
1 Department of Mathematics and Computer Science, Shahed University, Tehran 3319118651, Iran;  
1 [EMAIL_ADDRESS]  
[PERSON]  
2  
Footnote 2: email: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {ref: {  
supergrid graphs. In this paper, we focus on \(C\)-shaped supergrid graphs, which form a subclass of solid supergrid graphs. We will give the necessary and sufficient conditions for the Hamiltonicity and Hamiltonian connectivity of \(C\)-shaped supergrid graphs. We also present a linear-time algorithm for finding a longest path between any two distinct vertices in a \(C\)-shaped supergrid graph. The _two-dimensional integer grid graph_\(G^{\infty}\) is an infinite graph whose vertex set consists of all points of the Euclidean plane with integer coordinates and in which two vertices are adjacent if the (Euclidean) distance between them is 1. The _two-dimensional supergrid graph_\(S^{\infty}\) is an infinite graph obtained from \(G^{\infty}\) by adding all edges on the lines traced from up-left to down-right and from up-right to down-left. A graph is a _grid graph_ if it is a finite induced subgraph of \(G^{\infty}\). A _supergrid graph_ is a finite vertex-induced subgraph of \(S^{\infty}\). Supergrid graphs came from our industry-university cooperative research project, and can be applied to compute the stitching trace of computerized sewing machines [16]. A _solid supergrid graph_ is a supergrid graph without any hole, and a _rectangular supergrid graph_ is a solid supergrid graph bounded by a axis-parallel rectangle. A _\(L\)-shaped_ or _\(C\)-shaped_ supergrid graph is a supergrid graph obtained from a rectangular supergrid graph by removing a rectangular supergrid subgraph from it to form a \(L\)-like or \(C\)-like shape. The Hamiltonian connectivity and longest path of shaped supergrid graphs can be applied for computing the optimal stitching trace of computer embroidery machines [12; 16; 17]. For example, consider that a string of letters will be sewed into an object such that the number of crossed paths is minimum. The Hamiltonian connectivity and longest path of these shaped letters play an important role in deciding these sewing traces. In addition, they can be also applied to construct the minimum printing trace of 3D printers. For example, consider a 3D printer with a \(C\)-like object being printed. The software produces a series of thin layers, designs a path for each layer, combines these paths of produced layers, and transmits the above paths to 3D printer. Because 3D printing is performed layer-by-layer (see Figure 0(a)), each layer can be considered as a \(C\)-shaped supergrid graph. Suppose that there are \(k\) layers under the above 3D printing. If the Hamiltonian connectivity of \(C\)-shaped supergrid graphs holds true, then we can find a Hamiltonian path, starting from \(s_{i}\) and ending at \(t_{i}\), of a \(C\)-shaped supergrid graph \(C_{i}\), where \(C_{i}\), \(1\leqslant i\leqslant k\), represents a layer under 3D printing. Thus, we can design an optimal trace for the above 3D printing, where \(t_{i}\) is adjacent to \(s_{i+1}\) for \(1\leqslant i\leqslant k-1\). In this application, we restrict the 3D printer nozzle to be located at integer coordinates. For example, Figure 0(a) shows five layers \(C_{1}\)-\(C_{5}\) of a 3D printing for a \(C\)-type object, Figure 0(b) depicts the Hamiltonian paths of \(C_{i}\) for \(1\leqslant i\leqslant 5\), and the result of this 3D printing is shown in Figure 0(c). Some related works in the literature are summarized as follows. Recently, Hamiltonian path (cycle) and Hamiltonian connected problems in grid and supergrid graphs have received much attention. In [18], [PERSON] et al. proved that the Hamiltonian path problem on grid graphs is NP-complete. They also gave necessary and sufficient conditions for a rectangular grid graph having a Hamiltonian path between two given vertices.