For a planar graph G,
1. find the “polygon” of G (which has all of its edges adjacent to exterior region of planar graph), mark them g1.
2. For the remaining vertices, run step 1 and mark vertices of polygon with gi (where i is the iteration number), until there are no vertices left to make a polygon/triangle, that means, all remaining vertices are on a “line” (vertices which can’t form a “polygon”).
3. if remaining vertices are on a “line”, mark vertices of polygon with ge (where e is the iteration number).
4. end of step 1 to 3.
5. for each i= 1 to e, for each gi
6. if any vertex is marked “k”, move to next vertices.
7. if gi is adjacent to gi+1 ,then the other adjacent of gi is also adjacent to gi+1 and both these gi+1 marked are adjacent to each other(forming a square). Mark these 4 vertices “k”.
8. else if, such adjacency missed in any “level”, return false.
Every gi marked vertices on a polygon (polygon, which is equivalent to a circle, topologically) creates a “level” altogether. Informally, it can be said, these “levels” look like “orbit” of an atom.
The second part of the algorithm checks whether each “orbit”/ “polygon”/ “level” has consecutive vertices connecting next level which is a necessary condition to be Hamiltonian cycle.
Any idea why this would not work?
* A separate algorithm and proof for step 1 to 3 can be provided,check the remaining.