# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
A Hamiltonian cycle of \(R(m,3)\) is called _canonical_ if it contains three flat faces on two shorter boundaries and one longer boundary, and it contains one concave face on the other boundary, where the shorter boundary consists of three vertices. A Hamiltonian cycle of \(R(m,n)\) with \(n=2\) or \(n\geqslant 4\) is said to be _canonical_ if it contains three flat faces on three boundaries, and it contains one concave face on the other boundary. The following lemma states the result in [16] concerning the Hamiltonicity of rectangular supergrid graphs. **Lemma 1** (See [16]). : _Assume that \(R(m,n)\) is a rectangular supergrid graph with \(m\geqslant n\geqslant 2\). Then, the following statements hold true: \((1)\)\(R(m,3)\) contains a canonical Hamiltonian cycle; \((2)\)\(R(m,n)\) with \(n=2\) or \(n\geqslant 4\) contains four canonical Hamiltonian cycles with concave faces being on different boundaries._  
Figure 4 shows canonical Hamiltonian cycles for rectangular supergrid graphs found in Lemma 1. Each Hamiltonian cycle constructed by this lemma contains all the boundary edges on any three sides of the rectangular supergrid graph. This shows that for any rectangular supergrid graph \(R(m,n)\) with \(m\geqslant n\geqslant 4\), we can construct four canonical Hamiltonian cycles such that their concave faces are placed on different boundaries. For instance, the four distinct canonical Hamiltonian cycles of \(R(5,5)\) are shown in Figure 3(b)-e.  
Let \((G,s,t)\) denote supergrid graph \(G\) with two specified distinct vertices \(s\) and \(t\). Without loss of generality, we will assume that \(s_{x}\leqslant t_{x}\) in the rest of the paper. We denote a Hamiltonian path between \(s\) and \(t\) in \(G\) by \(HP(G,s,t)\). We say that \(HP(G,s,t)\) does exist if there is a Hamiltonian \((s,t)\)-path in \(G\). From Lemma 1, \(HP(R(m,n),s,t)\) does exist if \(m,n\geqslant 2\) and \((s,t)\) is an edge in the constructed Hamiltonian cycle of \(R(m,n)\). Figure 3: (**a**) A rectangular supergrid graph \(R(9,8)\), where the bold dashed lines indicate vertical and horizontal separations, (**b**) the structure of \(L\)-shaped supergrid graph \(L(9,11;6,8)\), and (**c**) the structure of \(C\)-shaped supergrid graph \(C(8,11;4,7;2,2)\). **Definition 2**. : _Assume that \(G\) is a connected supergrid graph and \(V_{1}\) is a subset of the vertex set \(V(G)\). \(V_{1}\) is called a vertex cut if \(G-V_{1}\) is disconnected. A vertex \(v\in V(G)\) is said to be a cut vertex if \(G-\{v\}\) is disconnected._  
In [12], the authors showed that \(HP(R(m,n),s,t)\) does not exist if the following condition hold:  
* \(s\) or \(t\) is a cut vertex, or \(\{s,t\}\) is a vertex cut (see Figure 5). Assume \(G\) is any supergrid graph. The following lemma shows that \(HP(G,s,t)\) does not exist if \((G,s,t)\) satisfies condition (F1), and can be verified by the same arguments in [23]. **Lemma 2** (See [23]). : _Assume that \(G\) is a supergrid graph with two vertices \(s\) and \(t\). If \((G,s,t)\) satisfies condition (F1), then \(HP(G,s,t)\) does not exist._  
The Hamiltonian \((s,t)\)-path of \(R(m,n)\) constructed in [12] satisfies that it contains at least one boundary edge of each boundary, and is called _canonical_. **Lemma 3** (See [12]). : _Assume \(R(m,n)\) is a rectangular supergrid graph and \(s,t\in V(R(m,n))\). If \((R(m,n),s,t)\) does not satisfy condition (F1), then there exists a canonical Hamiltonian \((s,t)\)-path of \(R(m,n)\)._  
**Lemma 4** (See [17]). : _Assume \(R(m,n)\) is a rectangular supergrid graph with \(m\geqslant 3\) and \(n\geqslant 2\), and \(s\) and \(t\) are its two distinct vertices. Let \(w=(1,1)\), \(z=(2,1)\), and \(f=(3,1)\).