# An attemt for detecting Planar-graph HamiltonianCycle.

• August 30th, 2014, 10:34 AM
jim198810
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 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.
• August 30th, 2014, 06:28 PM
MagiMaster
1 is wrong. The largest face of G does not need to be the outside border. Draw a triangle and then put lots of vertices in the middle. You can connect them to split the inside of the triangle in to two large faces while the outside face is still just 3 edges.

Try your algorithm on this graph: Take a hexagon and draw one triangle inside it connecting every other vertex. Add vertices to split each edge of the triangle. Draw another triangle between these 3 new vertices. (So 9 vertices and 15 edges in total.)
• August 30th, 2014, 06:42 PM
jim198810
Yes, "The largest face of G does not need to be the outside border." but I did not mean only the largest polygon but also edges or vertices on border.

Let me rephrase , "find the largest “polygon” of G which consists edges adjacent to exterior region of planar graph".
And you should get that I am trying to have an "orbit " like structure by step 1 to 3, it may be done other way, that's why I gave a footnote with * which you have missed completely!!
• August 31st, 2014, 12:51 AM
MagiMaster
I can only go by what you wrote. You haven't actually defined orbit anywhere. (And that footnote does not clarify anything.)

Also, the external face is unique. There's no largest or smallest. Unless by polygon you mean something different.
• September 1st, 2014, 07:11 PM
jim198810
OK... anything else??
• September 1st, 2014, 07:30 PM
MagiMaster
What happens when you run the algorithm on the graph I suggested?
• September 1st, 2014, 11:44 PM
jim198810
Image codes: hm

chk the image, {{0,1,2,3,4,5},{6,7,8}} are 2 levels/orbits.
• September 2nd, 2014, 03:02 PM
MagiMaster
That wasn't the graph I suggested. Using your numbering, here it is in adjacency list form:
Code:

```0 - 1 5 6 7 1 - 2 2 - 3 7 8 3 - 4 4 - 5 6 8 6 - 7 8 7 - 8```
• September 3rd, 2014, 09:23 PM
jim198810
Image codes: mm

{0,1,2,3,4,5},{7,6,8}... 2 levels/orbits....but does not satisfy due to step 7,8.
• September 3rd, 2014, 09:28 PM
MagiMaster
I can't really understand what step 7 is saying.
• September 3rd, 2014, 10:14 PM
jim198810
Image codes: hm

{{0,1,2,3,4,5},{6,7,8}} are 2 levels/orbits. vertex 2(a vertex of g1) is adjacent to 7(a vertex of g2), so 3(adjacent of 2) should be adjacent to 8 to be Hamiltonian circuit.
• September 4th, 2014, 04:34 AM
MagiMaster
I think I see. Try the graph:
Code:

```0 - 1 2 3 1 - 2 5 3 - 4 7 4 - 5 9 10 5 - 6 6 - 7 11 7 - 8 8 - 9 11 9 - 10 10 - 11```
Draw {0, 1, 2} as an outer triangle, {3, 4, 5, 6, 7} as a middle pentagon and {8, 9, 10, 11} as an inner square. Your algorithm should divide them in to those layers, but then there are no vertices that form a square between the outer and middle layer.
• September 5th, 2014, 05:02 AM
jim198810
Image codes: HM1

Is it a Hamiltonian Circuit?? Probably not....then

"but then there are no vertices that form a square between the outer and middle layer."

is not needed.
• September 5th, 2014, 01:32 PM
MagiMaster
Quote:

Originally Posted by jim198810
Image codes: HM1

Is it a Hamiltonian Circuit?? Probably not....then

"but then there are no vertices that form a square between the outer and middle layer."

is not needed.

Isn't that what step 7 is describing? Two adjacent vertices in layer x adjacent to two adjacent vertices in layer y? That would form a square (or at least a four sided polygon).
• September 5th, 2014, 10:54 PM
jim198810
yes , your graph fails to provide that so according to algo: , its not a HC.
• September 6th, 2014, 03:14 AM
MagiMaster
Except it does have a Hamiltonian cycle, namely: 0, 3, 7, 8, 9, 4, 10, 11, 6, 5, 1, 2, 0
• September 6th, 2014, 04:34 AM
jim198810
how you go from 11 to 6 without repeating?

chk image http://postimg.org/image/76af6ousz/2b86fac3/

Quote:

Draw {0, 1, 2} as an outer triangle, {3, 4, 5, 6, 7} as a middle pentagon and {8, 9, 10, 11} as an inner square. Your algorithm should divide them in to those layers, but then there are no vertices that form a square between the outer and middle layer.

computer does not visualize "inner" or "outer" ....... my algoruthm finds possible polygon with exterior region...it would find polygon {8,9,4,10,11} and {rest of the vertices}......set of vertex {7,8,11,6} would be obtained by step 7 so the graph is HC
• September 6th, 2014, 04:36 AM
MagiMaster
Quote:

Originally Posted by MagiMaster
Code:

```0 - 1 2 3 1 - 2 5 3 - 4 7 4 - 5 9 10 5 - 6 6 - 7 11 7 - 8 8 - 9 11 9 - 10 10 - 11```

11 should be connected to 6, not 7, though that doesn't change the fact that there are no squares between the outer layer and the middle layer.
• September 6th, 2014, 05:09 AM
jim198810
drawing mistake!! see below

Quote:

Originally Posted by jim198810

Quote:

Draw {0, 1, 2} as an outer triangle, {3, 4, 5, 6, 7} as a middle pentagon and {8, 9, 10, 11} as an inner square. Your algorithm should divide them in to those layers, but then there are no vertices that form a square between the outer and middle layer.

computer does not visualize "inner" or "outer" ....... my algoruthm finds possible polygon with exterior region...it would find polygon {8,9,4,10,11} and {rest of the vertices}......set of vertex {7,8,11,6} would be obtained by step 7 so the graph is HC

• September 6th, 2014, 02:15 PM
MagiMaster
You're going to have to define "the largest polygon of G" since, either it's the exterior face like your parenthetical remark indicates, or it'd be the Hamiltonian cycle itself. I see no reason to single out {8, 9, 4, 10 11}. It is neither a face, nor the largest cycle you can find.
• September 7th, 2014, 05:20 AM
jim198810
Quote:

Originally Posted by MagiMaster
You're going to have to define "the largest polygon of G" since, either it's the exterior face like your parenthetical remark indicates, or it'd be the Hamiltonian cycle itself. I see no reason to single out {8, 9, 4, 10 11}. It is neither a face, nor the largest cycle you can find.

and all of them must be attached to exterior region. Satisfying these conditions, the first polygon/level/orbit is {0,2,1,5,6,7,3}, you mark them , and look again among remaining vertices(now you don't consider {0,2,1,5,6,7,3}) , then the 2nd polygon is {8, 9, 4, 10 11}.

machine does not see like you so, "Inner" or "outer" might confuse you , but not the computer.
• September 7th, 2014, 01:39 PM
MagiMaster
I still don't understand why you single out those polygons. There's nothing special about them. {0,2,1,5,6,7,3} is not an exterior face. {8,9,4,10,11} would be after you remove {0,2,1,5,6,7,3}, but if you're marking exterior faces, that'd be {0,2,1}. The computer may see things differently, but you're still going to have to provide a step-by-step set of instructions on how to pick these cycles.
• September 8th, 2014, 03:05 AM
jim198810
Quote:

Originally Posted by MagiMaster
I still don't understand why you single out those polygons. There's nothing special about them. {0,2,1,5,6,7,3} is not an exterior face. .

Well , I have been quite specific about the polygon. The polygon must has all of its vertices,edges adjacent to exterior region. Can you find another polygon satisfying this condition in first iteration???({0,2,1} does not satisfy. 5 ,6,7,3 are also adjacent to exterior region, just because you draw them differently they don't get inside.That is why we chk graph Iso: in computer. I am sure you will get confused in lot of cases where you will identify them in a wrong way.)

question should be "how" (not "why") these polygons (satisfying given condition) can be found. You asked that too saying-

Quote:

Originally Posted by MagiMaster
, but you're still going to have to provide a step-by-step set of instructions on how to pick these cycles.

I said about this in the 1st post, chk ** mark below that post.I didn't include in this thread because it's quite big and there are 2 lemmas which need more rigorous argument. More over I have Not tried complicated large planer graph.At the moment Iam working on another thread(u know).

but assume I have or some can find the algo of finding such polygons in a planar graph, does the algo works?? or it has counterexamples?? that's all I wanted to know and started this thread.
• September 8th, 2014, 12:50 PM
MagiMaster
I don't think it's possible to say whether or not the algorithm works without the full details. (Well, generally speaking, it's highly unlikely that it works since the problem is NP-complete.) You haven't even provided your definition of exterior, but I'm pretty sure that you'll still be able to find a graph where it would not pick the right initial cycle and would falsely say that no Hamiltonian cycle exists.