1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids

Abstract

We give a complete structure theorem for $1$-complex $s,t$ Hamiltonian paths in rectangular grid graphs. We use the structure theorem to design an algorithm to reconfigure one such path into any other in linear time, making a linear number of switch operations in grid cells.