# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
Consider the positions of \(s\) and \(t\), as there are the following two subcases:  
Case 1.1: \(s_{x}>a\) or \(t_{x}>a\). Without loss of generality, assume that \(t_{x}>a\) and \(t_{y}=1\). We make a vertical and a horizontal separations on \(C(m,n;k,l;c,d)\) to obtain two disjoint supergrid subgraphs \(R_{2}=R(k,c)\) and \(R_{1}=L(m,n;k,c+l)\), as depicted in Figure 13a-c. Let \(p\in V(R_{1})\) and \(q\in V(R_{2})\) such that \(p\sim q\), \(q=(a+1,1)\), and \(p=(a,1)\) if \(s\
eq(a,1)\); otherwise \(p=(a,2)\) (see Figure 13a-c). Here, if \(|V(R_{2})|=1\) (i.e., \(k=1\)), then \(q=t\). Consider \((R_{1},s,p)\). Condition (F1) holds, if \(a=2\) and \(s_{y}=p_{y}\geqslant 2\), or \(p=(a,2)\) and \(s=(a,3)\). Clearly, in any case, it contradicts that \(p=(a,1)\) when \(s\
eq(a,1)\). Condition (F3) holds, if \(k>1\) and \(s_{x}\leqslant a\). If this case holds, then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F3), a contradiction. Condition (F4) holds, if \(n=3\), \(a=2\), \(k=1\), \(s=(1,n)\), and \(p=(a,2)\). It contradicts that \(p=(a,1)\) when \(s\
eq(a,1)\). Thus, \((R_{1},s,p)\) does not satisfy conditions (F1), (F3), and (F4). Now, consider \((R_{2},q,t)\). Since \(q=(a+1,1)\) and \(t=(m,1)\), clearly \((R_{2},q,t)\) does not satisfy condition (F1). A Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\) can be constructed by similar arguments in proving Lemma 8, as shown in Figure 13d. Case 1.2: \(s_{x},t_{x}\leqslant a\). In this subcase, \(k=1\) and hence \(a=m-1\). If \(k>1\), then \((C(m,n;k,l;c,d),s,t)\) satisfies (F3). Since \((C(m,n;k,l;c,d),s,t)\) does not satisfy condition (F8), \(s_{x}\
eq m-1\). There are two subcases:  
Case 1.2.1: \(s_{x},t_{x}<m-1\). Let \(z_{1}=(m-1,1)\), \(z_{2}=(m-1,2)\), and \(z_{3}=(m-1,3)\). Let \(e_{1}=(z_{1},z_{2})\) and \(e_{2}=(z_{2},z_{3})\). We make a vertical and horizontal separations on \(C(m,n;k,l;c,d)\) to obtain three disjoint rectangular supergrid subgraphs \(R_{1}=R(a,n)\)  
Figure 2:1 (a) A horizontal separation on \(C(m,n;k,l;c,d)\), (b) Hamiltonian paths \(P_{1}\) and \(P_{2}\) in \((R_{1},s,p)\) and \((R_{2},q,t)\), respectively, and (c) a Hamiltonian \((s,t)\)-path in \(C(m,n;k,l;c,d)\), where \(a=1\) and bold lines indicate the constructed Hamiltonian path. \(R_{2}=R(k,c)\), and \(R_{3}=R(k,d)\); as depicted in Figure 14a. Assume that \(v\in V(R_{2})\) and \(u\in V(R_{3})\). By Lemma 6, where \(a>2\), or Lemma 3, where \(a=2\), \(R_{1}\) contains a Hamiltonian \((s,t)\)-path \(P_{1}\) such that \(e_{1},e_{2}\in P_{1}\) (see Figure 14b). Then, \(P_{1}\), \(u\), \(v\) can be combined into a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\) by Statement (3) of Proposition 1 (see Figure 14c). Case 1.2.2: \(s_{x}<m-1\) and \(t_{x}=m-1\). Since \((C(m,n;k,l;c,d),s,t)\) does not satisfy conditions (F1), (F7), and (F8), we have that (1) \(t=(m-1,1)\) or \(t=(m-1,3)\) if \(m-1>2\), and (2) \(s_{y}=t_{y}=1\) or \(s_{y}=t_{y}=3\) if \(m-1=2\). Thus, \(t_{y}=1\) or \(t_{y}=3\). By symmetry, assume that \(t=(m-1,1)\). We make a vertical separation on \(C(m,n;k,l;c,d)\) to obtain two disjoint supergrid subgraphs \(R_{1}=R(m-2,n)\) and \(R_{2}=C(2,n;k,l;c,d)\), as depicted in Figure 14d,e. Let \(q\in V(R_{2})\) and \(p\in V(R_{1})\) such that \(p\thicksim q\), \(q=(m-1,3)\), and \(p=(m-2,3)\) if \(s\
eq(m-2,3)\); otherwise \(p=(m-2,2)\) (see Figure 14d,e). Notice that, here, if \(s=(m-2,3)\), then \(m\geqslant 4\). If \(m=3\) and \(s=(m-2,3)\), then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F8). Consider \((R_{2},q,t)\). Since \(a=d=c=1\), \(t=(m-1,1)\), and \(q=(m-1,3)\), clearly \((R_{2},q,t)\) does not satisfy conditions (F1), (F3), and (F9). Here, \((R_{2},q,t)\) lies on Lemma 8. Now, consider \((R_{1},s,p)\). Condition (F1) holds, if  
1. \(m-2=1\) and \(s=(m-2,2)\). In this case, \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F7), a contradiction. 2. \(m-2=2\) and \(s_{y}=p_{y}=2\). Clearly if \(s_{y}=2\), then \(p_{y}=3\). Hence, \(s_{y}\
eq p_{y}\). Therefore, \((R_{1},s,p)\) does not satisfy condition (F1).