# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 4 The Longest \((s,t)\)-Paths in C-Shaped Supergrid Graphs
Thus, a simple path between \(s\) and \(t\) can only go through one of these components. Therefore, its length cannot exceed the size of the largest component. Notice that, for (UB4), the length of any path between \(s\) and \(t\) is equal to \(\max\{\hat{L}(G_{1},s,t)+|V(G_{2})|,2\times(m-s_{x}+1)\}\) (see Figure 20c,d). Since \(a,c>1\), it is obvious that the length of any \((s,t)\)-path cannot exceed \(\hat{L}(G_{1},s,t)+|V(G_{2})|=\hat{L}(G_{1},s,t)+k\times c\). In the following, we will consider that \(a\geqslant 2\), and (\(c=1\) or \(d=1\)). Without loss of generality, assume that \(c=1\). We first make a horizontal and a vertical separation on \(C(m,n;k,l;c,d)\) to obtain two disjoint subgraphs \(G_{1}=L(m,n;k,l+c)\) and \(G_{2}=R(m-a,c)\), as depicted in Figure 21a, where \(a\geqslant 2\), \(c=1\), and \(G_{2}\) is a path graph. Depending the locations of \(s\) and \(t\), we consider the following cases:  
Figure 19: A longest \((s,t)\)-path under that \(a=1\) for (**a**,**b**) (UB1) holds, and (**c**,**d**) (UB2) holds, where the bold lines indicate the constructed longest \((s,t)\)-path and the bold dash lines indicate the separations. Figure 20: A longest \((s,t)\)-path under that \(a\geqslant 2\) and \(c,d\geqslant 2\) for (**a**,**b**) (UB3) holds, and (**c**,**d**) (UB4) holds, where the bold lines indicate the constructed longest \((s,t)\)-path. Case I: \(s,t\in G_{2}\). In this case, \(k>1\), \(s_{y}=t_{y}=1\), and \(a+1\leqslant s_{x},t_{x}\leqslant m\). Then, \((C(m,n;k,l;c,d),s,t)\) may satisfy conditions (F1) or (F3), as depicted in Figure 21b. Case II: \(s\in G_{1}\) and \(t\in G_{2}\). In this case, \((C(m,n;k,l;c,d),s,t)\) may satisfy conditions (F1) or (F3), as depicted in Figure 21c. Case III: \(s,t\in G_{1}\). In this case, \((C(m,n;k,l;c,d),s,t)\) may satisfy conditions (F1), (F3), (F7), or (F8), as depicted in Figure 21d. If \(d=1\), \(s_{y}=t_{y}=n\), and \(a+1\leqslant s_{x},t_{x}\leqslant m\), then it is the same as Case I. Depending on whether \((G_{1},s,t)\) satisfies condition (F1), there are the following three subcases:  
Case III.1: \(s\) or \(t\) is a cut vertex of \(G_{1}\). In this subcase, \(d=1\), and it is the same as Cases I or II. Case III.2: \(\{s,t\}\) is a vertex cut of \(G_{1}\). Consider the following subcases:  
Case III.2.1: \(\{s,t\}=\{(a,1),(a,2)\}\). In this subcase, \(k=1\) or \(k>1\), as shown in Figure 22a,b. If \(k>1\), then \((C(m,n;k,l;c,d),s,t)\) satisfies conditions (F1) and (F3); otherwise it satisfies condition (F1). Case III.2.2: \(a=2\), \(s_{y}=t_{y}\), and \(c+1\leqslant s_{x},t_{x}\leqslant c+l\). In this subcase, it is similar to condition (UB3) in Lemma 12 (see Figure 22c). Case III.2.3: \(d=2\), \(k>1\), \(a<s_{x}=t_{x}<m\), and \(n-1\leqslant s_{y},t_{y}\leqslant n\). In this subcase, it is similar to condition (UB4) in Lemma 12 (see Figure 22d). Case III.3: \((G_{1},s,t)\) does not satisfy condition (F1). In this subcase, \(s\) and \(t\) are not cut vertices and \(\{s,t\}\) is not a vertex cut of \(G_{1}\). Then, \((C(m,n;k,l;c,d),s,t)\) may satisfy conditions (F3), (F7), or (F8). Depending on the size of \(k\), we consider the following subcases:  
Case III.3.1: \(k=1\). In this subcase, \((C(m,n;k,l;c,d),s,t)\) may satisfy conditions (F7) and (F8), as follows:  
Case III.3.1: \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F7). In this subcase, \(a=2\) and \([(c=1\) and \(\{s,t\}=\{(1,1),(2,2)\}\) or \(\{(1,2),(2,1)\})\) or \((d=1\) and \(\{s,t\}=\{(1,n),(2,n-1)\}\) or \(\{(1,n-1),(2,n)\})\)\(]\) (see Figure 23a). Case III.3.1: \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F8). In this subcase, \(n=3\) and \(k=c=d=1\) (see Figure 23c-e). Case III.3.2: \(k>1\). In this subcase, \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F3) but it does not satisfy condition (F1). There are the following subcases:  
Case III.3.2.1: \(a=2\) and \([(c=1\) and \(\{s,t\}=\{(1,1),(2,2)\}\) or \(\{(1,2),(2,1)\})\) or \((d=1\) and \(\{s,t\}=\{(1,n),(2,n-1)\}\) or \(\{(1,n-1),(2,n)\})\)\(]\). In this subcase, it is the same as Case III.3.1.1 (see Figure 23b).