期刊名称：Lecture Notes in Engineering and Computer Science
印刷版ISSN：2078-0958
电子版ISSN：2078-0966
出版年度：2019
卷号：2239
页码：87-93
出版社：Newswood and International Association of Engineers
摘要：A supergrid graph is a finite vertex-induced subgraph
of the infinite graph whose vertex set consists of all points
of the plane with integer coordinates and in which two vertices
are adjacent if the difference of their x or y coordinates is
not larger than 1. The Hamiltonian path (cycle) problem is to
determine whether a graph contains a simple path (cycle) in
which each vertex of the graph appears exactly once. These
two problems are NP-complete for general graphs and they
are also NP-complete for general supergrid graphs. Despite the
many applications of the problem, they are still open for many
classes, including solid supergrid graphs and supergrid graphs
with some holes. A graph is called Hamiltonian connected if it
contains a Hamiltonian path between any two distinct vertices.
In this paper, first we will study the Hamiltonian cycle property
of C-shaped supergrid graphs, which are a special case of
rectangular supergrid graphs with a rectangular hole. Next,
we will show that C-shaped supergrid graphs are Hamiltonian
connected except few conditions. Finally, we will compute a
longest (s, t)-path between two distinct vertices s, t in linear time.
The Hamiltonian and longest (s, t)-paths 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.
