# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
For \((R_{2},s,t)\), we can construct two paths \(P_{21}\) and \(P_{22}\) such that \(P_{21}\) connects \(s\) and \(p\), \(P_{22}\) connects \(q\) and \(t\), \(V(P_{21})\cap V(P_{22})=\emptyset\), \(V(P_{21}\cup P_{22})=V(R_{2})\), \(p\sim w\), and \(q\sim z\), as shown in Figure 16a. Then, \(P=P_{21}\Rightarrow P_{1}\Rightarrow P_{22}\) forms a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\) (see Figure 16a). Case 2.1.2.2: \(a>3\). We make a vertical separation on \(R_{2}\) to obtain two disjoint subgraphs \(R_{21}=R(m^{\prime},n_{2})\) and \(R_{22}=L(n_{2},m-m^{\prime};1,1)\), where \(m^{\prime}=s_{x}\) if \(s_{x}<a-1\); otherwise \(m^{\prime}=s_{x}-1\); as shown in Figure 16b,c. First, let \(s,t\in R_{21}\) and consider Figure 16b. Clearly since \(s_{x}=t_{x}=m^{\prime}\), \((R_{21},s,t)\) does not satisfy condition (F1). By Lemma 3, \(R_{21}\) contains a canonical Hamiltonian \((s,t)\)-path \(P_{21}\). Then, there exists one edge \(e_{21}\in P_{21}\) that is placed to face \(R_{1}\). By Theorem 2, \(R_{22}\) and \(R_{1}\) contain Hamiltonian cycle \(HC_{22}\) and \(HC_{1}\), respectively. Using the algorithm of [17], we can construct \(HC_{22}\) and \(HC_{1}\) to satisfy that one flat face of \(HC_{1}\), which is placed to face \(R_{21}\) and \(R_{22}\), and one flat face of \(HC_{22}\), which is placed to face \(R_{1}\) (see Figure 16d). Then, there exist four edges \(e_{1},e_{2}\in HC_{1}\), \(e_{21}\in P_{21}\), and \(e_{22}\in HC_{22}\) such that \(e_{1}\approx e_{21}\) and \(e_{2}\approx e_{22}\). By Statements (1) and (2) of Proposition 1, \(P_{21}\), \(HC_{1}\), and \(HC_{22}\) can be combined into a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\). The construction of a such Hamiltonian path is depicted in Figure 16e. Now, let \(s,t\in R_{22}\) and consider Figure 16c. Since \(s_{x}=t_{x}=1\) and \(s_{x},t_{x}<a\) (in \(R_{22}\)), it is clear that \((R_{22},s,t)\) does  
Figure 2:4 (**a–c**) A horizontal separation on \(C(m,n;k,l;c,d)\) for \(n>3\), (**d**) a Hamiltonian \((s,t)\)-path in \(R_{2}\) and a Hamiltonian cycle in \(R_{1}\), and (**e**) a Hamiltonian \((s,t)\)-path in \(C(m,n;k,l;c,d)\). not satisfy conditions (F1), (F3), and (F4). By similar arguments in proving \(s,t\in R_{21}\), a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\) can be constructed (see Figure 16f). Case 2.2: (\(s\in R_{1}\) and \(t\in R_{2}\)) or (\(t\in R_{1}\) and \(s\in R_{2}\)). Without loss of generality, assume that \(t\in R_{1}\) and \(s\in R_{2}\). Let \(q\in V(R_{1})\) and \(p\in V(R_{2})\) such that \(p\sim q\), where  
\[ \begin{cases}p=(1,n_{2})\text{ and }q=(1,n_{2}+1),&\text{if }s\
eq(1,n_{2}) \text{ and }t\
eq(1,n_{2}+1);\\ p=(2,n_{2})\text{ and }q=(2,n_{2}+1),&\text{if }s=(1,n_{2})\text{ and }t=(1,n_{2}+1);\\ p=(2,n_{2})\text{ and }q=(1,n_{2}+1),&\text{if }s=(1,n_{2})\text{ and }t\
eq(1,n_{2}+1);\\ p=(1,n_{2})\text{ and }q=(2,n_{2}+1),&\text{otherwise.}\end{cases} \]  
Consider \((R_{2},s,p)\) and \((R_{1},q,t)\). Condition (F1) holds, if  
(i) \((n_{2}=2\) and \(s_{x}=p_{x}=2)\) or \((n-n_{2}=2\) and \(q_{x}=t_{x}=2)\). Obviously in this case, \(s_{x}=p_{x}=2\) and \(q_{x}=t_{x}=2\). It contradicts that \(p_{x}=q_{x}=1\) when \(s_{x}\
eq 1\) and \(t_{x}\
eq 1\). (ii) \(k>1\) and \(a<s_{x},t_{x}<m\). If this case holds, then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F1), a contradiction. Condition (F3) holds, if \(k>1\) and \(s_{x},t_{x}\leqslant a\). If this case holds, then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F3), a contradiction. Condition (F4) holds, if \(a=2\) and \([(n_{2}>2\) and \(s_{y},p_{y}\leqslant 2)\) or \((n-n_{2}>2\) and \(q_{y},t_{y}\geqslant n-1)]\). A simple check shows that these cases do not occur. Therefore, \((R_{2},s,p)\) and \((R_{1},q,t)\) do not satisfy conditions (F1), (F3), and (F4). A Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\) can be constructed by similar arguments in proving Lemma 8. Notice that, here, \(R_{1}\) and \(R_{2}\) are \(L\)-shaped supergrid graphs.