A Continuation of Spanning 2-Connected Subgraphs in Truncated Rectangular Grid Graphs

Abstract

A grid graph is a finite induced subgraph of the infinite 2-dimensional grid defined by $\mathbb{Z}\times \mathbb{Z}$ and all edges between pairs of vertices from $\mathbb{Z}\times \mathbb{Z}$ at Euclidean distance precisely $1$. An $m\times n$-rectangular grid graph is induced by all vertices with coordinates from $1$ to $m$ and from $1$ to $n$, respectively. A natural drawing of a (rectangular) grid graph $G$ is obtained by drawing its vertices in ${\mathbb{R}}^2$ according to their coordinates. We consider a subclass of the rectangular grid graphs obtained by deleting some vertices from the corners. Apart from the outer face, all (inner) faces of these graphs have area one (bounded by a $4$-cycle) in a natural drawing of these graphs. We determine which of these graphs contain a Hamilton cycle, i.e., a cycle containing all vertices, and solve the problem of determining a spanning $2$-connected subgraph with as few edges as possible for all these graphs.