1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
Rahnuma Islam Nishat, Venkatesh Srinivasan, Sue H. Whitesides · Journal of Graph Algorithms and Applications · 2023
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.