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.
Best Answer
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:
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.