# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
By Lemmas 3 and 8, \(R_{1}\) and \(R_{2}\) contain Hamiltonian \((s,p)\)-path \(P_{1}\) and \((q,p)\)-path \(P_{2}\), respectively. Then, \(P=P_{1}\Rightarrow P_{2}\) forms a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\), as depicted in Figure 14f. Case 2: \(n>3\). Since \(n>3\) and \(c=d=1\), it follows that \(l>1\). We make a horizontal separation on \(C(m,n;k,l;c,d)\) to obtain two disjoint supergrid subgraphs \(R_{1}=L(m,n-n_{2};k,l_{1})\) and \(R_{2}=L(n_{2},m;l_{2},k)\), where \(n_{2}=c+l-1\), \(l_{1}=c+l-n_{2}\), and \(l_{2}=l-l_{1}\) (see Figure 15a-c). Since \(n_{2}=c+l-1\) and \(d=1\), clearly \(n-n_{2}=2\). Also since \(n-n_{2}=2\) and \(n>3\), it follows that \(n_{2}\geqslant 2\). Depending on the positions of \(s\) and \(t\), there are the following two subcases:  
Case 2.1: \(s,t\in R_{1}\) or \(s,t\in R_{2}\). Without loss of generality, assume that \(s,t\in R_{2}\). Here, \(k=1\). If \(k>1\), then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F3). Case 2.1.1: \((n_{2}>2)\) or \((n_{2}=2\) and \([(s_{x}\
eq t_{x})\) or \((s_{x}=t_{x}=1)])\). Since \(k=1\), it is enough to show that \((R_{2},s,t)\) does not satisfy conditions (F1) and (F4). Condition (F1) holds, if  
1. \(2\leqslant s_{x}=t_{x}\leqslant a\). By assumption, this case does not occur. Figure 2:2 (a) A vertical and a horizontal separation on \(C(m,n;k,l;c,d)\) under that \(s_{x},t_{x}<m-1\), (b) a Hamiltonian \((s,t)\)-path in \(R_{1}\) for (a), (c) a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\) for (a), (d,e) a vertical separation on \(C(m,n;k,l;c,d)\) for \(s_{x}<m-1\) and \(t_{x}=m-1\), and (f) a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\) for (d), where the bold lines indicate the constructed Hamiltonian path and \(\otimes\) represents the destruction of an edge while constructing a Hamiltonian cycle. Figure 2:3 (a–c) A vertical and a horizontal separation on \(C(m,n;k,l;c,d)\) under that \(a\geqslant 2\), \(c=d=1\), \(n=3\), and \(t_{x}>a\), and (d) a Hamiltonian \((s,t)\)-path in \(C(m,n;k,l;c,d)\) for (a), where bold lines indicate the constructed Hamiltonian path. * \(a=2\) and \(2\leqslant s_{y}=t_{y}\leqslant n_{2}\). Clearly if this case holds, then \((C(m,n;k,l;c,d),\,s,t)\) satisfies condition (F1), a contradiction. Condition (F4) holds, if \(a=2\), \(n_{2}>2\), \(s_{x},t_{x}\leqslant 2\), \(s_{y},t_{y}\leqslant 2\), \(s_{x}\
eq t_{x}\), and \(s_{y}\
eq t_{y}\). Clearly, if this case holds, then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F7), a contradiction. Therefore, \((R_{2},s,t)\) does not satisfy conditions (F1), (F3), and (F4). Since \((R_{2},s,t)\) does not satisfy conditions (F1), (F3), and (F4). By Theorem 1, \(R_{2}\) contains a Hamiltonian \((s,t)\)-path \(P_{2}\) in which one edge \(e_{2}\) is placed to face \(R_{1}\). By Theorem 2, \(R_{1}\) contains a Hamiltonian cycle \(HC_{1}\) such that its one flat face is placed to face \(R_{2}\). Then, there exist two edges \(e_{1}\in HC_{1}\) and \(e_{2}\in P_{2}\) such that \(e_{1}\approx e_{2}\) (see Figure 15d). By Statement (2) of Proposition 1, \(P_{2}\) and \(HC_{1}\) 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 15e. Case 2.1.2: \(n_{2}=2\) and \(s_{x},t_{x}>1\). In this case, \(n=4\), \(a>2\), \(l=2\), and \(2\leqslant s_{x}=t_{x}\leqslant a-1\). If \(s_{x}=t_{x}=a\), then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F1). Depending on whether \(a=3\), we consider the following two subcases:  
Case 2.1.2.1: \(a=3\). In this subcase, we can construct a Hamiltonian \((s,t)\)-path by the pattern shown in Figure 16a. Consider Figure 16a. Since \(w=(1,3)\) and \(z=(3,3)\), clearly \((R_{1},w,z)\) does not satisfy conditions (F1), (F3), and (F4). Thus by Theorem 1, \(R_{1}\) contains a Hamiltonian \((w,z)\)-path \(P_{1}\).