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

• October 21st 2013, 03:49 PM
Aeris130
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.
• October 21st 2013, 09:50 PM
SlipEternal
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).
• October 22nd 2013, 07:42 AM
Aeris130
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.
• October 22nd 2013, 07:52 AM
SlipEternal
Re: Possible to find unbounded face cycles based on planar embeddings? [Graph]
Then no.