# 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
Then, \(P=P_{2}\Rightarrow P_{1}\) (resp. \(P_{1}\Rightarrow P_{2}\)) forms a longest \((s,t)\)-path of \(C(m,n;k,l;c,d)\). Figures 19c,d and 24c,d show the constructions of such a longest \((s,t)\)-path. Case 3: Conditions (UB3), (UB8), or (UB9) hold. Assume that (UB3) holds. By Lemma 12, \(\hat{U}(C(m,n;k,l;c,d),s,t)=\max\{\hat{L}(G_{11},s,t),\hat{L}(G_{12},s,t)\}\), where \(G_{11}=L(m,n^{\prime};k,l^{\prime})\), \(G_{12}=L(s_{y},m;k^{\prime},k)\), \(n^{\prime}=n-s_{y}+1\), \(l^{\prime}=n^{\prime}-d\), and \(k^{\prime}=s_{y}-1\) (see Figure 20a,b). Since \(G_{11}\) and \(G_{12}\) are \(L\)-shaped supergrid graphs, by the algorithm of [17] we can construct a longest path between \(s\) and \(t\) in \(G_{11}\) and \(G_{12}\). Figure 20a,b depicts such a construction. For conditions (UB8) and (UB9), consider Figure 25c-f. Then, \(G_{12}\) may be a rectangle. By the algorithm of [12] we can construct a longest \((s,t)\)-path in \(G_{12}\) if it is a rectangle. In addition, \(G_{11}\) is a \(C\)-shaped supergrid graph in (UB9) (see Figure 25e). Then, \((G_{11},s,t)\) satisfies condition (UB12). Its longest \((s,t)\)-path can be computed by the algorithm in [17]. Its construction is shown in Case 6 and Figure 25e shows such a construction of the longest \((s,t)\)-path. Case 4: Condition (UB4) holds. By Lemma 12, \(\hat{U}(C(m,n;k,l;c,d),s,t)=\hat{L}(G_{1},s,t)+|V(G_{2})|=\hat{L}(G_{1},s,t)+k \times c\), where \(G_{1}=L(m,n;k,l+c)\) and \(G_{2}=R(k,c)\). Consider Figure 20c,d. Then, \(G_{1}\) is a \(L\)-shaped supergrid graph and \(G_{2}\) is a rectangle. By the algorithm of [17], we can construct a longest \((s,t)\)-path \(P_{1}\) in \(G_{1}\) that contains edge \(e_{1}\) locating to face \(G_{2}\). By Lemma 1, \(G_{2}\) contains a canonical Hamiltonian cycle \(HC_{2}\) such that its one flat face is placed to face \(G_{1}\). Thus, by Statement (2) of Proposition 1, \(P_{1}\) and \(HC_{2}\) can be combined into a longest \((s,t)\)-path of \(C(m,n;k,l;c,d)\). Case 5: Condition (UB5) holds. By Lemma 13, \(\hat{U}(C(m,n;k,l;c,d),s,t)=t_{x}-s_{x}+1\). Obviously, the lemma holds for the single possible path between \(s\) and \(t\) (see Figure 24a,b). Case 6: Condition (UB12) holds. By Lemma 13, \(\hat{U}(C(m,n;k,l;c,d),s,t)=\hat{L}(G_{1},s,t)+1\), where \(G_{1}=L(m,n;k,l+c)\). We make a vertical and a horizontal separation on \(C(m,n;k,l;c,d)\) to obtain two disjoint supergrid subgraphs \(R_{2}=L(n_{2},m_{2};1,1)\) and \(R(m,n;k,l;c,d)\), where \(n_{2}=c+l\) and \(m_{2}=a+1\) (see Figure 27a). Note that \((C(m,n;k,l;c,d),\)\(s,t)\) does not satisfy condition (F1) in this case. Depending on the positions of \(s\) and \(t\), these are the following three subcases:  
Case 6.1: \(s,t\in R_{1}\). A longest \((s,t)\)-path of \((C(m,n;k,l;c,d)\) can be constructed by similar arguments in proving Case 1 of Lemma 10 (see Figure 27c,d). Then, we can construct a Hamiltonian \((s,t)\)-path of \(R_{1}\cup R_{2}\). Figure 27a,b depicts such constructions. The size of constructed Hamiltonian \((s,t)\)-path equals to \(\hat{L}(L(m,n;k,l+c))+1=|V(R_{1}\cup R_{2})|\), and hence it is the longest \((s,t)\)-path of \((C(m,n;k,l;c,d)\). Case 6.2: \(s,t\in R_{2}\). A longest \((s,t)\)-path of \((C(m,n;k,l;c,d)\) can be constructed by similar arguments in proving Case 2 of Lemma 10 (see Figure 27c,d). Depending on whether \(\{s,t\}\) is a vertex cut of \(R_{2}\), we consider Figure 27c,d. Then, we can construct a Hamiltonian \((s,t)\)-path of \(R_{1}\cup R_{2}\), as shown in Figure 27a,b. The size of constructed Hamiltonian \((s,t)\)-path equals to \(\hat{L}(L(m,n;k,l+c))+1=|V(R_{1}\cup R_{2})|\), and hence it is the longest \((s,t)\)-path of \((C(m,n;k,l;c,d)\). Case 6.3: \((s\in R_{1}\) and \(t\in R_{2})\) or \((s\in R_{2}\) and \(t\in R_{1})\). Without loos of generality, assume that \(s\in R_{1}\) and \(t\in R_{2}\). A longest \((s,t)\)-path of \((C(m,n;k,l;c,d)\) can be constructed by similar arguments in proving Case 2 of Lemma 9 and Case 3 of Lemma 10.