The Hamiltonicity, Hamiltonian Connectivity, and Longest (s, t)-path of L-shaped Supergrid Graphs

arXiv1904.02581MaRDI QIDQ6316698FDOQ6316698

Fatemeh Keshavarz-Kohjerdi, Ruo-Wei Hung

Publication date: 4 April 2019

Abstract: Supergrid graphs contain grid graphs and triangular grid graphs as their subgraphs. The Hamiltonian cycle and path problems for general supergrid graphs were known to be NP-complete. A graph is called Hamiltonian if it contains a Hamiltonian cycle, and is said to be Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices in it. In this paper, we first prove that every L-shaped supergrid graph always contains a Hamiltonian cycle except one trivial condition. We then verify the Hamiltonian connectivity of L-shaped supergrid graphs except few conditions. The Hamiltonicity and Hamiltonian connectivity of L-shaped supergrid graphs can be applied to compute the minimum trace of computerized embroidery machine and 3D printer when a L-like object is printed. Finally, we present a linear-time algorithm to compute the longest (s, t)-path of L-shaped supergrid graph given two distinct vertices s and t.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

This page was built for publication: The Hamiltonicity, Hamiltonian Connectivity, and Longest (s, t)-path of L-shaped Supergrid Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6316698)