Thread: 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₁.
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.

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.)

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!!

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.

OK... anything else??

What happens when you run the algorithm on the graph I suggested?

Image codes: hm


chk the image, {{0,1,2,3,4,5},{6,7,8}} are 2 levels/orbits.

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

Image codes: mm

{0,1,2,3,4,5},{7,6,8}... 2 levels/orbits....but does not satisfy due to step 7,8.

I can't really understand what step 7 is saying.

Image codes: hm


{{0,1,2,3,4,5},{6,7,8}} are 2 levels/orbits. vertex 2(a vertex of g₁) is adjacent to 7(a vertex of g₂), so 3(adjacent of 2) should be adjacent to 8 to be Hamiltonian circuit.

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.

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.

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).

yes , your graph fails to provide that so according to algo: , its not a HC.

Except it does have a Hamiltonian cycle, namely: 0, 3, 7, 8, 9, 4, 10, 11, 6, 5, 1, 2, 0

how you go from 11 to 6 without repeating?

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

Originally Posted by MagiMaster

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

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.

drawing mistake!! see below

Originally Posted by jim198810

Originally Posted by MagiMaster

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

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.

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.

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.

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-

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.

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.