# 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
Since \(c=1\), the larger component will be \(G_{1}=L(m,n;k,l+c)\). For (UB8) and (UB9), consider Figure 25c-f. The computations of their upper bounds are the same as (UB7), and (UB3) in Lemma 12. For (UB10), consider Figure 26a-c. A simple check shows that the length of any \((s,t)\)-path cannot exceed \(\hat{L}(G_{a},s,p)+\hat{L}(G_{b},q,t)=\hat{L}(L(m,n;k,l+c),s,t)\), where \(G_{a}\), \(G_{b}\), \(p\), \(q\) are defined in Figure 26a-c. For (UB11), consider Figure 26d-f. In Figure 26d-f, let \(r=(a,1)\) and \(z=(a,2)\), where \(r,z\) may be one of \(s\) and \(t\). Removing \(r\) and \(z\) clearly disconnects \(C(m,n;k,l;c,d)\) into two components and a simple path between \(s\) and \(t\) can only go through a component that contains \(s\), \(t\), \(r\), and \(z\). Since the one disjoint component contains only one vertex, the upper bound of the longest \((s,t)\)-path will be \(\hat{L}(L(m,n;k,l+c),s,t)\). For (UB12), consider Figure 26g,h. Since \(w\) is a cut vertex, we can easily show that the length of any path between \(s\) and \(t\) cannot exceed \(\hat{L}(G_{1},s,t)+1\), where \(G_{1}=L(m,n;k,l+c)\) or \(L(n,m;l+d,k)\). Assume that condition (C0) is defined as follows:  
(C0) \((C(m,n;k,l;c,d),s,t)\) does not satisfy any of conditions (F1), (F3), (F7), (F8), and (F9). Clearly \((C(m,n;k,l;c,d),s,t)\) must satisfy one of conditions (C0), (UB1), (UB2), (UB3), (UB4), (UB5), (UB6), (UB7), (UB8), (UB9), (UB10), (UB11), and (UB12). If \((C(m,n;k,l;c,d),s,t)\) satisfies (C0), then \(\hat{U}(C(m,n;k,l;c,d),s,t)=|V(C(m,n;k,l;c,d))|=mn-kl\). Otherwise, \(\hat{U}(C(m,n;k,l;c,d),s,t)\) can be computed using Lemmas 11-13. We summarize them as follows:  
Figure 25: The longest \((s,t)\)-path under that \(a\geqslant 2\) and \(c=1\), where (**a,b**) (UB7) holds, (**c,d**) (UB8) holds, and (**e,f**) (UB9) holds. Figure 26: The longest \((s,t)\)-path under that \(a\geqslant 2\) and \(c=1\), where (**a–c**) (UB10) holds, (**d–f**) (UB11) holds, and (**g,h**) (UB12) holds. \[\hat{U}(C(m,n;k,l;c,d),s,t)= \begin{cases}\hat{L}(G_{1},s,t),&\text{if (UB1), (UB7), (UB10), or}\\ &\text{(UB11) holds;}\\ \hat{L}(G_{1},s,z)+\hat{L}(G_{2},w,t),&\text{if (UB2) or (UB6) holds;}\\ \max\{\hat{L}(G_{11},s,t),\hat{L}(G_{12},s,t)\},&\text{if (UB3), (UB8), or}\\ &\text{(UB9) holds;}\\ \hat{L}(G_{1},s,t)+k\times c,&\text{if (UB4) holds;}\\ t_{x}-s_{x}+1,&\text{if (UB5) holds;}\\ L(G_{1},s,t)+1,&\text{if (UB12) holds;}\\ mn-kl,&\text{if (C0) holds.}\end{cases} \]  
In the following, we will show how to obtain a longest \((s,t)\)-path for C-shaped supergrid graphs. Notice that if \((C(m,n;k,l;c,d),s,t)\) satisfies condition (C0), then, by Theorem 5, it contains a Hamiltonian \((s,t)\)-path. Lemma 14: _If \((C(m,n;k,l;c,d),s,t)\) satisfies one of the conditions_ (UB1)-(UB12)_, then \(\hat{L}(C(m,n;k,l;c,d),s,t)=\hat{U}(C(m,n;k,l;c,d),s,t)\)._  
Proof: We prove this lemma by constructing a \((s,t)\)-path \(P\) such that its length equals to \(\hat{U}(C(m,n;k,l;c,d),s,t)\). Consider the following cases:  
Case 1: Condition (UB1), (UB7), (UB10), or (UB11) holds. Then, by Lemma 11 (resp. Lemma 13), \(\hat{U}(C(m,n;k,l;c,d),s,t)=\hat{L}(G_{1},s,t)\), where \(G_{1}=L(m,n-c;k,l)\) or \(G_{1}=L(c+1,m;1,k)\) (resp. \(G_{1}=L(m,n;k,l+c)\) or \(G_{1}=L(n,m;l+d,k)\)) (see Figures 19a,b, 25a,b and 26a-f). Since \(G_{1}\) is a \(L\)-shaped supergrid graph, by the algorithm of [17], we can construct a longest \((s,t)\)-path in \(G_{1}\). Case 2: Condition (UB2) or (UB6) holds. By Lemma 11 (resp. Lemma 13), \(\hat{U}(C(m,n;k,l;c,d),s,t)=\hat{L}(G_{1},s,z)+\hat{L}(G_{2},w,t)\) (see Figures 19c,d and 24c,d), where \(G_{1}=L(m,n-c;k,l)\), \(G_{2}=R(m,c)\) (resp. \(G_{1}=L(m,n;k,l+c)\) and \(G_{2}=R(k,c)\)), and \(z\thicksim w\). Then, \(G_{1}\) and \(G_{2}\) are \(L\)-shaped and rectangular supergrid graphs, respectively. First, by the algorithms [12; 17], we can construct a longest \((s,z)\)-path \(P_{2}\) (resp. \(P_{1}\)) in \(G_{2}\) (resp. \(G_{1}\)) and a longest \((w,t)\)-path \(P_{1}\) (resp. \(P_{2}\)) in \(G_{1}\) (resp. \(G_{2}\)), respectively.