Establishes structural conditions for Hamiltonian paths in rectangular grid graphs with a triangular hole, extending classical grid-graph results.

Overview

This project investigates Hamiltonian paths in rectangular grid graphs that contain a single triangular hole—one of the simplest non-orthogonal obstacles that disrupts the well-understood structure of classical grids. While prior work completely characterizes Hamiltonicity for solid rectangles and for grids with rectangular holes, little is known when the hole is triangular. To study this systematically, I introduced a parametrized geometric model for triangular holes using stacked thin reversed T-shapes. This representation allows different triangle placements and orientations to be analyzed uniformly and captures how the hole interacts with snake-like traversal patterns typically used in rectangular grids.

Using a combination of parity arguments and decompositions into 2-rectangles, I proved a new impossibility condition: when the triangular hole partitions the grid into two subregions each containing an odd number of vertices, a Hamiltonian path cannot exist. I then constructed explicit Hamiltonian paths for many feasible configurations, including most placements near the grid boundary. These results provide both necessary conditions and constructive solutions for a family of grid-with-hole instances that had not previously been classified.