2022/05/16 by Nishat, Rahnuma Islam, Srinivasan, Venkatesh, Whitesides, Sue
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2205.08025
A simple s,t path P in a rectangular grid graph \mathbbG is a Hamiltonian path from the top-left corner s to the bottom-right corner t such that each internal subpath of P with both endpoints a and b on the boundary of \mathbbG has the minimum number of bends needed to travel from a to b (i.e., 0, 1, or 2 bends, depending on whether a and b are on opposite, adjacent, or the same side of the bounding rectangle). Here, we show that P can be reconfigured to any other simple s,t path of \mathbbG by switching 2× 2 squares, where at most 5|\mathbbG|/4 such operations are required. Furthermore, each square-switch is done in O(1) time and keeps the resulting path in the same family of simple s,t paths. Our reconfiguration result proves that the Hamiltonian path graph \calG for simple s,t paths is connected and has diameter at most 5|\mathbbG|/4 which is asymptotically tight.