An attemt for detecting Planar-graph HamiltonianCycle.

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 g_{1}.

2. For the remaining vertices, run step 1 and mark vertices of polygon with g_{i} (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 g_{e} (where e is the iteration number).

4. end of step 1 to 3.

5. for each i= 1 to e, for each g_{i}

6. if any vertex is marked “k”, move to next vertices.

7. if g_{i} is adjacent to g_{i+1} ,then the other adjacent of g_{i }is also adjacent to g_{i+1} and both these g_{i+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 g_{i} 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.