Results 1 to 4 of 4

Math Help - Possible to find unbounded face cycles based on planar embeddings? [Graph]

  1. #1
    Newbie
    Joined
    Oct 2013
    From
    Sweden
    Posts
    2

    Possible to find unbounded face cycles based on planar embeddings? [Graph]

    Given a set of face cycles computed from a planar embedding (consisting of a clockwise ordered adjacency list for each vertex in a connected graph component), is it possible to determine the unbounded face?

    Visually it's easy to confirm since the unbounded cycle will be traversed on the opposite clockwise direction as the remaining cycles. But in terms of moving from one edge to the next in the unbounded face, the edge selection conforms to the same clockwise ordering as the remaining faces in the embedding.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Possible to find unbounded face cycles based on planar embeddings? [Graph]

    I am assuming the graph is a planar graph. This method will not work for a planar embedding of a nonplanar graph. Every edge is adjacent to exactly two faces. Given a single edge v_iv_j of a bounded face, it will be traversed by v_jv_i in its adjacent face. So, turn it into a binary vector space. Let v_iv_j + v_jv_i = 0. After adding all face cycles together, whatever is left is guaranteed to be the face cycle of the unbounded cycle (just traversed in the opposite direction).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2013
    From
    Sweden
    Posts
    2

    Re: Possible to find unbounded face cycles based on planar embeddings? [Graph]

    The graph is indeed planar. Maybe I wasn't clear in my first post, but the set of faces computed from the planar embedding includes the unbounded face (I'm just trying to find out which one it is), so I can't do any traversal based on only bounded faces.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Possible to find unbounded face cycles based on planar embeddings? [Graph]

    Then no.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: March 30th 2012, 03:27 AM
  2. Replies: 5
    Last Post: December 22nd 2010, 02:42 AM
  3. is this graph planar?
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: March 3rd 2010, 02:32 PM
  4. isomorphic graph, planar graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 09:13 AM
  5. Find Max Value Based on F' Graph
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 20th 2009, 04:41 PM

Search Tags


/mathhelpforum @mathhelpforum