For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles I have asked the question at Math SE and at SO, but I can't seem to get the answer I want. So I paraphrase the question and it here.

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 edges to complete cycles. Given Vertex $V$, edge $E$, there are $C=E−V+1$ number of cycles ( Euler formula), 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.

One of the suggestion I got from Math SE is to use planar embedding algorithm to "guess" the most natural coordinates for each vertex ( so that the graph looks "nice" visually), and then construct the polygonal faces. But this is exceptionally long-winded. I believe that this problem can be tackled more simply without involving coordinates.
Construct a planar embedding and use all but one of the faces of the embedding as cycles in the cycle basis. (It doesn't matter which one you leave out.)

Note that there are actually two different subproblems in planar embedding: determining the cyclic ordering of the edges around each vertex, and computing explicit coordinates. But for the cycle basis, you only need the cyclic ordering, since that's what determines the structure of the faces; you don't need any kind of "nice" coordinates.

Finding planar embeddings is linear time but complicated; there are several standard algorithms.