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.

Infectious diseases, such as COVID-19, SARS, MERS, etc., have seriously endangered human safety, economy, and education. During the spread of epidemics, restricting the range of activities of personnel is one of the options for the prevention and treatment of infectious diseases. A global navigation satellite system (GNSS), it can provide accurate coordinates of latitude and longitude to targets with GNSS receivers. However, it is not common to use GNSS coordinates to represent positions in social life. For epidemic management, it is important to know the locations (and addresses) of targets, especially in social life. When there are many targets, it is not easy to efficiently map these coordinates to locations. Therefore, we propose a GNSS-based crowd-sensing strategy for specific geographical areas that can be used to calculate how many targets are in specific geographical areas or whether a target is in a specific area. This strategy is based on the coordinates of latitude and longitude provided by GNSS to find the locations of these coordinates. As simulated data, the data records containing latitude and longitude in a well-known social networking service platform are used. The strategy is also available for mining hot spots or hot areas.

Supergrid graphs are derived by computing stitch paths for computerized embroidery machines. In the past, we have studied the Hamiltonian-related properties of supergrid graphs and their subclasses of graphs. In this paper, we propose a generalized graph class for supergrid graphs called extended supergrid graphs. Extended supergrid graphs include grid graphs, supergrid graphs, diagonal supergrid graphs, and triangular supergrid graphs as subclasses of graphs. In this paper, we study the problems of domination and independent domination on extended supergrid graphs. A dominating set of a graph is the subset of vertices on it, such that every vertex of the graph is in this set or adjacent to at least a vertex of this set. If any two vertices in a dominating set are not adjacent, this is called an independent dominating set. Domination and independent domination problems find a dominating set and an independent dominating set with the least number of vertices on a graph, respectively. The domination and independent domination set problems on grid graphs are known to be NP-complete, meaning that these two problems on extended supergrid graphs are also NP-complete. However, the complexities of these two problems in other subclasses of graphs remain unknown. In this paper, we first prove that these two problems on diagonal supergrid graphs are NP-complete, then, by a simple extension, we prove that these two problems on supergrid graphs and triangular supergrid graphs are also NP-complete. In addition, these two problems on rectangular supergrid graphs are known to be linearly solvable; however, the complexities of these two problems on rectangular triangular-supergrid graphs remain unknown. This paper provides tight upper bounds on the sizes of the minimum dominating and independent dominating sets for rectangular triangular-supergrid graphs.

During a widespread epidemic, a large portion of the population faces an increased risk of contracting infectious diseases such as COVID-19, monkeypox, and pneumonia. These outbreaks often trigger cascading effects, significantly impacting society and healthcare systems. To contain the spread, the Centers for Disease Control and Prevention (CDC) must monitor infected individuals (targets) and their geographical locations (areas) as a basis for allocating medical resources. This scenario is a Target-to-Area (TTA) problem. Previous research introduced the Point-In-Polygon (PIP) technique to address multi-target and single-area TTA problems. PIP technology relies on an area’s boundary points to determine whether a target is within that region. However, when dealing with multi-target, multi-area TTA problems, PIP alone may have limitations. The K-Nearest Neighbors (KNN) algorithm presents a promising alternative, but its classification accuracy depends on the availability of sufficient samples, i.e., known targets and their corresponding geographical areas. When sample data are limited, the effectiveness of KNN is constrained, potentially delaying the CDC’s ability to track and manage outbreaks. For this problem, this study proposes an improved approach that integrates PIP and KNN technologies while introducing area boundary points as additional samples. This enhancement aims to improve classification accuracy and mitigate the impact of insufficient sample data on epidemic tracking and management.