# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results  
In this section, we will introduce some terminologies and symbols. Some observations and previously established results for the Hamiltonicity and Hamiltonian connectivity of rectangular and \(L\)-shaped supergrid graphs are also given. In addition, we also prove some Hamiltonian connectivity property of a special class of rectangular supergrid graphs that will be used in proving our result. Suppose that \(G\) is a graph with vertex set \(V(G)\) and edge set \(E(G)\). Let \(S\subseteq V(G)\), and let \(u,v\in V(G)\). We write \(G[S]\) for the subgraph of \(G\)_induced_ by \(S\), and \(G-S\) for the subgraph \(G[V(G)-S]\). In general, we write \(G-v\) instead of \(G-\{v\}\). The notation \(u\thicksim v\) (resp., \(u\thicksim v\)) means that vertices \(u\) and \(v\) are adjacent (resp., non-adjacent). A vertex \(w\)_adjoints_ edge \((u,v)\) if \(w\thicksim u\) and \(w\thicksim v\). For two edges \(e_{1}=(u_{1},v_{1})\) and \(e_{2}=(u_{2},v_{2})\), if \(u_{1}\thicksim u_{2}\) and \(v_{1}\thicksim v_{2}\) then we say that \(e_{1}\) and \(e_{2}\) are _parallel_, denoted this by \(e_{1}\thickapprox e_{2}\). A _neighbor_ of vertex \(v\) is any vertex adjacent to \(v\). We denote by \(N_{G}(v)\) the set of neighbors of \(v\) in \(G\), and let \(N_{G}[v]=N_{G}(v)\cup\{v\}\). The _degree_ of vertex \(v\) in \(G\), denoted by \(deg(v)\), is the number of vertices adjacent to \(v\). A path \(P\) of length \(|P|\) in \(G\), denoted by \(v_{1}\to v_{2}\rightarrow\cdots\rightarrow\overline{v_{|P|-1}}\rightarrow \overline{v_{|P|}}\), is a sequence \((v_{1},v_{2},\cdots,v_{|P|-1},v_{|P|})\) of vertices such that \((v_{i},v_{i+1})\in E(G)\) for \(1\leqslant i<|P|\), and all vertices except \(v_{1},v_{|P|}\) in it are distinct. The first and last vertices  
Figure 1: **(a)** The five layers \(C_{1}\)–\(C_{5}\) of a 3D printing model while printing a \(C\)-type object, **(b)** the computing Hamiltonian path from \(s_{i}\) to \(t_{i}\) of each layer \(C_{i}\) in **(a)**, and **(c)** the final result while performing the five-layered 3D printing. visited by \(P\) are denoted by \(start(P)\) and \(end(P)\), respectively. We will use \(v_{i}\in P\) to denote \"\(P\) visits vertex \(v_{i}\)\" and use \((v_{i},v_{i+1})\in P\) to denote \"\(P\) visits edge \((v_{i},v_{i+1})\)\". A path from \(v_{1}\) to \(v_{k}\) is denoted by \((v_{1},v_{k})\)-path. In addition, we use \(P\) to refer to the set of vertices visited by path \(P\) if it is understood without ambiguity. A cycle is a path \(C\) with \(|V(C)|\geqslant 3\) and \(start(C)=end(C)\). Two paths (or cycles) \(P_{1}\) and \(P_{2}\) of graph \(G\) are _vertex-disjoint_ if \(V(P_{1})\cap V(P_{2})=\emptyset\). If \(end(P_{1})\thicksim start(P_{2})\), then two vertex-disjoint paths \(P_{1}\) and \(P_{2}\) can be concatenated into a path, denoted by \(P_{1}\Rightarrow P_{2}\). For a node (vertex) \(v\) in the plane with integer coordinates, let \(v_{x}\) and \(v_{y}\) represent the \(x\) and \(y\)_coordinates_ of node \(v\), respectively, denoted by \(v=(v_{x},v_{y})\). A _grid graph_ is a finite vertex-induced subgraph of \(G^{\infty}\). Figure 1(a) shows a grid graph, and it is clear that the maximum degree of all vertices is four. A _supergrid graph_ is a finite vertex-induced subgraph of \(S^{\infty}\). Figure 1(b) depicts a supergrid graph, it is clear that the maximum degree of all vertices is eight. Thus, supergrid graphs contain grid graphs as subgraphs. Notice that grid graphs are not a subclass of supergrid graphs, and the converse is also true. Obviously, all grid graphs are bipartite [18] but supergrid graphs are not bipartite. A _rectangular supergrid graph_, denoted by \(R(m,n)\), is a supergrid graph whose vertex set is \(V(R(m,n))=\{v=(v_{x},v_{y})|1\leqslant v_{x}\leqslant m\text{ and }1\leqslant v_{y}\leqslant n\}\). That is, \(R(m,n)\) contains \(m\) columns and \(n\) rows of vertices in \(S^{\infty}\) and its shape is a rectangle. The size of \(R(m,n)\) is defined to be \(mn\), and \(R(m,n)\) is called \(n\)-rectangle.