# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
Lemma 10: _Assume \(a(=m-k)>1\), \((c>1\) or \(d>1)\), and \((C(m,n;k,l;c,d),s,t)\) does not satisfy conditions (F1), (F3), (F7), and (F8). Then \(HP(C(m,n;k,l;c,d),s,t)\) does exist._  
Proof: Without loss of generality, assume that \(d>1\). Since \(d>1\), \(c\geqslant 1\), and \(l\geqslant 1\), thus \(n\geqslant 4\). We make a horizontal separation on \(C(m,n;k,l;c,d)\) to obtain two disjoint supergrid subgraphs \(R_{2}=L(n_{2},m;l,k)\) and \(R_{1}=R(m,n-n_{2})\), where \(n_{2}=c+l\) and \(n-n_{2}=d\) (see Figure 17a,b). Since \(n\geqslant 4\), \(n_{2}=c+l\), \(c,l\geqslant 1\), and \(d>1\), it follows that \(n-n_{2},n_{2}\geqslant 2\). Depending on the positions of \(s\) and \(t\), there are the following three subcases:  
Case 1: \(s,t\in R_{1}\). In this case, \((c>1)\) or \((c=1\) and \(k=1)\). If \(c=1\) and \(k>1\), then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F3), a contradiction. Depending on the size of \(n-n_{2}\), we consider the following two subcases:  
Case 1.1: \((n-n_{2}>2)\) or \((n-n_{2}=2\) and \([(s_{x}\
eq t_{x})\), \((s_{x}=t_{x}=1)\), or \((s_{x}=t_{x}=m)])\). In this subcase, \(\{s,t\}\) is not a vertex cut of \(R_{1}\). Then, \((R_{1},s,t)\) does not satisfy condition (F1). By Lemma 3, \(R_{1}\) contains a canonical Hamiltonian \((s,t)\)-path \(P_{1}\). Using the algorithm of [12], we can construct a Hamiltonian \((s,t)\)-path \(P_{1}\) of \(R_{1}\) in which one edge \(e_{1}\) is placed to face \(R_{2}\). By Theorem 2, \(R_{2}\) contains a Hamiltonian cycle \(HC_{2}\). Using the algorithm of [17], we can construct \(HC_{2}\) such that its one flat face is placed to face \(R_{1}\). Then, there exist two edges \(e_{1}\in P_{1}\) and \(e_{2}\in HC_{2}\) such that \(e_{1}\approx e_{2}\) (see Figure 17c). By Statement (2) of Proposition 1, \(P_{1}\) and \(HC_{2}\) 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 17d. Case 1.2: \(n-n_{2}=2\) and \(1<s_{x}=t_{x}<m\). In this subcase, \(\{s,t\}\) is a vertex cut of \(R_{1}\). Notice that, here, \(s_{x},t_{x}\leqslant a\). If \(s_{x},t_{x}>a\) and \(k>1\), then \((C(m,n;k,l;c,d),s,t)\)  
Figure 17: (**a,b**) A horizontal separation on \(C(m,n;k,l;c,d)\) under that \(a>1\) and \(d>1\), (**c**) a Hamiltonian \((s,t)\)-path in \(R_{1}\) and a Hamiltonian cycle in \(R_{2}\), and (**d**) a Hamiltonian \((s,t)\)-path in \(C(m,n;k,l;c,d)\) for (**c**). satisfies condition (F1). Without loss of generality, assume that \(s_{y}<t_{y}\). We make a vertical and a horizontal separations on \(R_{1}\) to obtain two disjoint supergrid subgraphs \(R_{11}=L(s_{x},n-n_{2};1,1)\) and \(R_{12}=R_{1}-R_{11}\). Let \(p\in V(R_{12})\), \(q\in V(R_{11})\), and \(w,z\in V(R_{2})\) such that \(p\sim z\), \(q\sim w\), \(q=(1,n_{2}+1)\), \(w=(1,n_{2})\), \(p=(s_{x}+1,n_{2}+1)\), and \(z=(s_{x},n_{2})\) (see Figure 18a,b). A simple check shows that \((R_{12},s,p)\), \((R_{2},z,w)\), and \((R_{11},q,t)\) do not satisfy conditions (F1), (F3), and (F4). Thus, by Theorem 1, \(R_{12}\), \(R_{2}\), and \(R_{11}\) contain a Hamiltonian \((s,p)\)-path \(P_{12}\), Hamiltonian \((z,w)\)-path \(P_{2}\), and Hamiltonian \((q,t)\)-path \(P_{11}\), respectively. Then, \(P=P_{12}\Rightarrow P_{2}\Rightarrow P_{11}\) forms a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\). The construction of a such Hamiltonian path is depicted in Figure 18c. Case 2: \(s,t\in R_{2}\). A Hamiltonian \((s,t)\)-path of \((C(m,n;k,l;c,d)\) can be constructed by similar arguments in proving Case 2.1 of Lemma 9. Notice that, in this case, \(R_{1}\) is a rectangular supergrid graph. Case 3: (\(s\in R_{1}\) and \(t\in R_{2}\)) or (\(s\in R_{2}\) and \(t\in R_{1}\)). A Hamiltonian \((s,t)\)-path of \((C(m,n;k,l;c,d)\) can be constructed by similar arguments in proving Case 2.2 of Lemma 9. Notice that, in this case, \(R_{1}\) is a rectangular supergrid graphs. It immediately follows from Lemmas 7-10 that the following theorem holds true.