Finding Hamiltonian and Longest (s,t)-Paths of C-Shaped Supergrid Graphs in Linear Time

Fatemeh Keshavarz-Kohjerdi | Ruo-Wei Hung

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=159287
Date :  2022/02/13
Publish in :    Algorithms

Link :  https://www.mdpi.com/1999-4893/15/2/61
Keywords :Hamiltonicity, Hamiltonian connectivity, longest (s, t)-path, C-shaped supergrid graphs, computer embroidery machines, 3D printers

Abstract :

---

A graph is called Hamiltonian connected if it contains a Hamiltonian path between any two distinct vertices. In the past, we proved the Hamiltonian path and cycle problems for general supergrid graphs to be NP-complete. However, they are still open for solid supergrid graphs. In this paper, first we will verify the Hamiltonian cycle property of C-shaped supergrid graphs, which are a special case of solid supergrid graphs. Next, we show that C-shaped supergrid graphs are Hamiltonian connected except in a few conditions. For these excluding conditions of Hamiltonian connectivity, we compute their longest paths. Then, we design a linear-time algorithm to solve the longest path problem in these graphs. The Hamiltonian connectivity of C-shaped supergrid graphs can be applied to compute the optimal stitching trace of computer embroidery machines, and construct the minimum printing trace of 3D printers with a C-like component being printed.