A note on the subgraphs of the (2×∞)(2×∞)-grid

We give a linear-time algorithm checking whether a graph is a subgraph of the (2×k)(2×k)-grid for some value of kk. Our algorithm is based on a detailed characterization of the structure of such graphs.