English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

A supergrid graph is a finite vertex-induced subgraph of the infinite graphwhose vertex set consists of all points of the plane with integer coordinatesand in which two vertices are adjacent if the difference of their x or ycoordinates is not larger than 1. The Hamiltonian path (cycle) problem is todetermine whether a graph contains a simple path (cycle) in which each vertexof the graph appears exactly once. This problem is NP-complete for generalgraphs and it is also NP-complete for general supergrid graphs. Despite themany applications of the problem, it is still open for many classes, includingsolid supergrid graphs and supergrid graphs with some holes. A graph is calledHamiltonian connected if it contains a Hamiltonian path between any twodistinct vertices. In this paper, first we will study the Hamiltonian cycleproperty of C-shaped supergrid graphs, which are a special case of rectangularsupergrid graphs with a rectangular hole. Next, we will show that C-shapedsupergrid graphs are Hamiltonian connected except few conditions. Finally, wewill compute a longest path between two distinct vertices in these graphs. TheHamiltonian connectivity of C-shaped supergrid graphs can be applied to computethe optimal stitching trace of computer embroidery machines, and construct theminimum printing trace of 3D printers with a C-like component being printed.

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