The Hamiltonian connectivity of rectangular supergrid graphs |
| |
Affiliation: | 1. Department of Computer Science and Information Engineering, Chaoyang University of Technology, Wufeng, Taichung 41349, Taiwan;2. Department of Information and Communication Engineering, Chaoyang University of Technology, Wufeng, Taichung 41349, Taiwan;3. Department of Computer Science, Shenyang Aerospace University, 37 DaoYi South Street, DaoYi economic development Zone Shenyang City, Liaoning Province 110000, China |
| |
Abstract: | A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph. |
| |
Keywords: | Hamiltonian connectivity Longest path Rectangular supergrid graph Grid graph Computer sewing machine |
本文献已被 ScienceDirect 等数据库收录! |
|