For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles In a planar graph $G$, one can easily find all the cycle basis by first finding the spanning tree ( any spanning tree would do), and then use the remaining edge to complete cycles. Given Vertex $V$, edge $E$, there are $C=E-V+1$ number of cycles, and there are $C$ number of edges that are inside the graph, but not inside the spanning tree.
Now, there always exists a set of cycle basis such that each and every edge inside the $G$ is shared by at most 2 cycles. My question is, is there any algorithm that allows me to find such a set of cycle basis? The above procedure I outlined only guarantees to find a set of cycle basis, but doesn't guarantee that all the edges in the cycle basis is shared by at most two cycles.
Note: Coordinates for each vertex are not known, even though we do know that the graph must be planar. 

I agree with all the commenters who say that you should just find a planar embedding. However, I happened to stumble across a description that might make you happy:

Let $G$ be a three-connected
  planar graph and let $C$ be a cycle.
  Let $G/C$ be the graph formed by
  contracting $C$ down to a point. Then
  $C$ is a face of the planar graph if
  and only if $G/C$ is two-connected.

In particular, this lemma is useful in proving that a three-connected graph can only be planar in one way, a result of Whitney.
But testing this for every cycle is much less efficient than just finding the planar embedding.
