# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
The vertex \(v\) is called the _upper-left_ (resp., _upper-right_, _down-left_, _down-right_) _corner_ of \(R(m,n)\) if for any vertex \(w=(w_{x},w_{y})\in R(m,n)\), \(w_{x}\geqslant v_{x}\) and \(w_{y}\geqslant v_{y}\) (resp., \(w_{x}\leqslant v_{x}\) and \(w_{y}\geqslant v_{y}\), \(w_{x}\geqslant v_{x}\) and \(w_{y}\leqslant v_{y}\), \(w_{x}\leqslant v_{x}\) and \(w_{y}\leqslant v_{y}\)). The edge \((u,v)\) is said to be _horizontal_ (resp., _vertical_) if \(u_{y}=v_{y}\) (resp., \(u_{x}=v_{x}\)), and is called _crossed_ if it is neither a horizontal nor a vertical edge. There are four boundaries in a rectangular supergrid graph \(R(m,n)\) with \(m,n\geqslant 2\). The edge in the boundary of \(R(m,n)\) is called _boundary edge_. A path is called _boundary_ of \(R(m,n)\) if it visits all vertices and edges of the same boundary in \(R(m,n)\) and its length equals to the number of vertices in the visited boundary. For example, Figure 2(a) shows a rectangular supergrid graph \(R(9,8)\) which is called \(8\)-rectangle and contains \(2\times(8+7)=30\) boundary edges. Figure 2(a) also indicates the types of edges and corners. In the figures we will assume that \((1,1)\) are coordinates of the upper-left corner in \(R(m,n)\), except when we explicitly change this assumption. A _\(L\)-shaped supergrid graph_, denoted by \(L(m,n;k,l)\), is a supergrid graph obtained from a rectangular supergrid graph \(R(m,n)\) by cutting its subgraph \(R(k,l)\) from the upper-right corner, where \(m,n>1\) and \(k,l\geqslant 1\). A _C-shaped supergrid graph_\(C(m,n;k,l;c,d)\) is a supergrid graph obtained from a rectangular supergrid graph \(R(m,n)\) by removing its subgraph \(R(k,l)\) from its node coordinated as \((m,c+1)\) while \(R(m,n)\) and \(R(k,l)\) have exactly one border side in common, where \(m\geqslant 2\), \(n\geqslant 3\), \(k,l\geqslant 1\), \(c\geqslant 1\), \(d=n-l-c\geqslant 1\), and \(a=m-k\geqslant 1\). The structures of \(L(m,n;k,l)\) and \(C(m,n;k,l;c,d)\) are explained in Figure 2(b),\(c\), respectively. Figure 2: (a) A grid graph and (b) a supergrid graph, where the circles represent the vertices and the solid lines indicate the edges in the graphs. In our method, we need to partition a rectangular or \(C\)-shaped supergrid graph into \(\eta\) disjoint parts, where \(\eta\geqslant 2\). The partition is defined as follows. **Definition 1**. : _Assume that \(\hat{G}\) is a rectangular supergrid graph \(R(m,n)\) or a \(C\)-shaped supergrid graph \(C(m,n;k,l;c,d)\). A separation operation on \(\hat{G}\) is a partition of \(\hat{G}\) into \(\eta\) vertex-disjoint rectangular or \(L\)-shaped supergrid subgraphs \(\hat{G_{1}}\), \(\hat{G_{2}}\), \(\cdots\), \(\hat{G_{\eta}}\), i.e., \(V(\hat{G})=V(\hat{G_{1}})\cup V(\hat{G_{2}})\cup\cdots\cup V(\hat{G_{\eta}})\) and \(V(\hat{G_{i}})\cap V(\hat{G_{j}})=\emptyset\) for \(i\
eq j\) and \(1\leqslant i,j\leqslant\eta\), where \(\eta\geqslant 2\). A separation is called horizontal if it consists of a set of vertical edges, and is called vertical if it contains a set of horizontal edges. Note that horizontal or vertical separation may be empty in our partition for the presentation of clarity. For example, Figure 2(a) indicates a horizontal (resp., vertical) separation of \(R(9,8)\) which partitions it into \(R(9,3)\) and \(R(9,5)\) (resp., \(R(4,8)\) and \(R(5,8)\))._  
Let \(R(m,n)\) be a rectangular supergrid graph with \(m\geqslant n\geqslant 2\), \(\mathcal{C}\) be a cycle of \(R(m,n)\), and let \(H\) be a boundary of \(R(m,n)\). The restriction of \(\mathcal{C}\) to \(H\) is denoted by \(\mathcal{C}_{|H}\). If \(|\mathcal{C}_{|H}|=1\), i.e., \(\mathcal{C}_{|H}\) is a boundary path on \(H\), then \(\mathcal{C}_{|H}\) is called _flat face_ on \(H\). If \(|\mathcal{C}_{|H}|>1\) and \(\mathcal{C}_{|H}\) contains at least one boundary edge of \(H\), then \(\mathcal{C}_{|H}\) is called _concave face_ on \(H\).