## 4 Intractable Problems on a (Unit) Grid Intersection Graph
### The Hamiltonian Cycle Problem  
We give two hardness results for grid intersection graphs in this section. **Theorem 11**: _The Hamiltonian cycle problem is \(\mathcal{NP}\)-complete for unit grid intersection graphs._  
Proof. It is clear that the problem is in \(\mathcal{NP}\). Hence we show \(\mathcal{NP}\)-hardness. We show a similar reduction in [57]. We start from the Hamiltonian cycle problem in planar directed graph with degree bound two, which is still \(\mathcal{NP}\)-hard [58]. Let \(G_{0}=(V_{0},A)\) be a planar directed graph with degree bound two. (We deal with directed graphs only in this proof; we will use \((u,v)\) as a directed edge, called _arc_, which is distinguished from \(\{u,v\}\).) As shown in [57, 58], we can assume that \(G_{0}\) consists of two types of vertices: (type \(\triangle\)) with indegree two and outdegree one, and (type \(\bigtriangledown\)) with indegree one and outdegree two. Hence, the set \(V_{0}\) of vertices can be partitioned into two sets \(V_{\triangle}\) and \(V_{\bigtriangledown}\) that consist of the vertices in type \(\triangle\) and \(\bigtriangledown\), respectively. Moreover, we have two more claims; (1) the unique arc from a type \(\triangle\) vertex has to be the unique arc to a type \(\bigtriangledown\) vertex; and (2) each of two arcs from a type \(\bigtriangledown\) vertex has to be one of two arcs to a type \(\triangle\) vertex. If the unique arc from a type \(\triangle\) vertex \(v\) is into one of a type \(\triangle\) vertex \(u\), the vertex \(u\) has to be visited from \(v\) to make a Hamiltonian cycle. Hence the vertex \(u\) can be replaced by an arc from \(v\) to the vertex \(w\) which is pointed from \(u\). On the other hand, if one of two arcs from a type \(\bigtriangledown\) vertex \(v\) reaches another type \(\bigtriangledown\) vertex \(u\), the vertex \(u\) should be visited from \(v\). Hence the other arc \(a\) from \(v\) can be removed from \(G_{0}\). Then the vertex \(w\) incident to \(a\) has degree 2. Hence we have two cases; \(w\) can be replaced by an arc, or we can conclude \(G_{0}\) does not have a Hamiltonian cycle. Repeating these processes, we have the claims (1) and (2), which imply that we have \(|V_{\triangle}|=|V_{\bigtriangledown}|\), the underlying graph of \(G_{0}\) is bipartite (with two sets \(V_{\triangle}\) and \(V_{\bigtriangledown}\)), and any cycle contains two types of vertices alternately. By the claims, we can partition arcs into two groups; (1) arcs from a type \(\triangle\) vertex to a type \(\bigtriangledown\) vertex called _thick arcs_, and (2) arcs from a type \(\bigtriangledown\) vertex to a type \(\triangle\) vertex called _thin arcs_. By above discussion, we can observe that any Hamiltonian cycle has to contain all thick arcs (Moreover, contracting thick arcs, we can show \(\mathcal{NP}\)-completeness of the Hamiltonian cycle problem even if we restrict ourselves to the directed planar graphs that only consist of vertices of two outdegrees and two indegrees.) Now, we construct a unit grid intersection graph \(G_{1}=(V_{1},E_{1})\) from \(G_{0}=(V_{0},A)\) which satisfies the above conditions. One type \(\bigtriangledown\) vertex is represented by five vertical lines and two horizontal lines, and one type \(\triangle\) vertex is represented by three vertical lines and one horizontal line in Figure 4 (each corresponding line segments are in gray area). Each thick arc is represented by alternations of one parallel vertical line and one parallel horizontal line in Figure 4, and each thin arc is represented by alternations of two parallel vertical lines and two parallel horizontal lines in Figure 5. The vertices are joined by the arcs in a natural way. An example is illustrated in Figure 6.  
Figure 4: Reduction of thick arcs. Figure 5: Reduction of thin arcs. For the resultant graph \(G_{1}\), it is obvious that the reduction can be done in a polynomial time, and \(G_{1}\) is a unit grid intersection graph. Hence we show \(G_{0}\) has a Hamiltonian cycle if and only if \(G_{1}\) has a Hamiltonian cycle.