Notices
Results 1 to 24 of 24

Thread: An attemt for detecting Planar-graph HamiltonianCycle.

  1. #1 An attemt for detecting Planar-graph HamiltonianCycle. 
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    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.


    Last edited by jim198810; September 7th, 2014 at 05:46 AM.
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.)


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    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!!
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  6. #5  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    OK... anything else??
    Reply With Quote  
     

  7. #6  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    What happens when you run the algorithm on the graph I suggested?
    Reply With Quote  
     

  8. #7  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    Image codes: hm


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

  9. #8  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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
    Reply With Quote  
     

  10. #9  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    Image codes: mm

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

  11. #10  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I can't really understand what step 7 is saying.
    Reply With Quote  
     

  12. #11  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    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.
    Reply With Quote  
     

  13. #12  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  14. #13  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    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.
    Reply With Quote  
     

  15. #14  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Quote Originally Posted by jim198810 View Post
    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).
    Reply With Quote  
     

  16. #15  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    yes , your graph fails to provide that so according to algo: , its not a HC.
    Reply With Quote  
     

  17. #16  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Except it does have a Hamiltonian cycle, namely: 0, 3, 7, 8, 9, 4, 10, 11, 6, 5, 1, 2, 0
    Reply With Quote  
     

  18. #17  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    how you go from 11 to 6 without repeating?

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


    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
    Last edited by jim198810; September 6th, 2014 at 05:01 AM.
    Reply With Quote  
     

  19. #18  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Quote Originally Posted by MagiMaster View Post
    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.
    Reply With Quote  
     

  20. #19  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    drawing mistake!! see below


    Quote Originally Posted by jim198810 View Post


    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
    Reply With Quote  
     

  21. #20  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  22. #21  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    Quote Originally Posted by MagiMaster View Post
    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.
    Reply With Quote  
     

  23. #22  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  24. #23  
    Forum Freshman
    Join Date
    Aug 2014
    Posts
    30
    Quote Originally Posted by MagiMaster View Post
    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 View Post
    , 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.
    Last edited by jim198810; September 8th, 2014 at 06:01 AM.
    Reply With Quote  
     

  25. #24  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

Similar Threads

  1. Detecting "Crossing" in GraphIsomorphism
    By jim198810 in forum Computer Science
    Replies: 26
    Last Post: September 14th, 2014, 01:22 PM
  2. Detecting a spaceship with today's sensor tech?
    By icewendigo in forum Astronomy & Cosmology
    Replies: 2
    Last Post: May 31st, 2012, 12:08 PM
  3. Cancer cell detecting machine
    By s09tp2 in forum Health & Medicine
    Replies: 0
    Last Post: February 14th, 2011, 12:45 AM
  4. Detection of submarines via gravity detecting satellite?
    By maddbiker in forum Military Technology
    Replies: 3
    Last Post: March 22nd, 2009, 01:58 PM
  5. Detecting Scalar Waves
    By Clarky in forum Personal Theories & Alternative Ideas
    Replies: 1
    Last Post: September 5th, 2005, 07:01 PM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •