I'm trying to code an algorithm to get the faces of an undirected graph. The graph I receive in the input is known to be planar and biconnected. However, the graph's adjacency list isn't ordered in any way (clockwise or counterclockwise).
I have done some research on the subject and some StackOverflow threads suggest to do a planar embedding of the graph. I have found this article: Efficient Planarity Testing, written by Tarjan and Hopcroft. This article describes the edge-addition algorithm.
On the other hand, I find the code quite laborious just to verify the planarity of a graph. I don't want to draw the graph, I don't care if there are many embeddings, I just want to list the faces of my graph. To do so, I need a way to order my edges. However the article doesn't specify any clockwise ordering per se, but it does show a subprocess whose job is to order the edge (Section 5, p. 8), it doesn't seem to order in clockwise, but by their LOWPT values.
My question is: is there any algorithm to sort my edge or do I have to produce a planar embedding of a graph, which I already know is planar and biconnected?
Thank you