Finding the longest path on the grid pattern to lock the smartphones using the Hamiltonian path

Smartphone is the latest-generation handheld device as it contributes a lot to ease our daily activities such as communication, keeping personal data, office-tasks, and even many fun-activities! Nowadays, it's an important thing for the smartphone users to keep their smartphones secured to prevent unwanted accidents. There are few trending ways to keep the devices secured during locking or unlocking like pin-code, fingerprint, or pattern-code on a grid graph. There is a so-called "mobile device security industry" is growing up since the last few years to research about the finest & strongest security ways.

According to the trend, I am going to summarize the Hamiltonian path problem to find the longest path of the mesh graph to lock/unlock our phones. Before getting start, let's revise few basic theories to know about the mesh graph.

Graph

A Graph (G) includes 02 sets V and E, where V is the set of vertices and E is the set of pairs of vertices called edges. An edge is said to be incident to the vertices if it joins. Graph G = (V , E) is called a simple graph if every pair of vertices has at most one edge that is incident to these two vertices and there is no loop (a, a) ∈ E for any a ∈ V.

You can find more details explanation about graph theory here to understand the theory as well.

Grid Graph

A grid (also known as mesh or lattice) graph denotes a drawing which is embedded in a Euclidean space like grid graph or triangular grid graph. This article focuses on the grid graph because it's using as the graphical pattern to lock or unlock phones. We are going to review few algorithms to find the longest path in the grid due to increase a complex security. I have attached the following picture of lock/unlock pattern which is also called a 3×3 grid graph.

Grid (or, mesh) graphs are regular graphs, meaning that each edge has the same weight or represents the same distance in Euclidean space as in other spaces.

Hamiltonian path problem

The longest path problem is a well-known NP-complete Hamiltonian path problem, i.e. deciding whether there is a simple path that visits each vertex of the graph exactly once, is a special case of the longest path problem. The rectangular grid graph R(n, m) is the subgraph of G∞ (the infinite grid graph) induced by V(m, n)={υ|1≤ vx ≤m, 1 ≤vy ≤n}, where vx and vy are respectively x and y coordinates of v. The Hamiltonian path problem has been studied for grid graphs, where it's proved that the problem for general grid graphs is NP-complete. You can find a deep study where several theories are stated to explain the problem. The Hamiltonian path problem is noted as an algorithm as following.

As a complete example, the construction of a longest path between s and t in R(12, 5) is shown step by step below:

This is a linear-time algorithm for finding a longest path in a rectangular grid graph between any two given vertices which can be used to lock/unlock smartphones to increase the security.