For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles
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.