How to do a clockwise ordering of a planar graph in order to define its faces? I am currently making an algorithm for planar graphs that I need to triangulate so they become maximally planar (that is triangulated and planar) given only the lists of neighbors for each node : no coordinates or anything.
The only way I have been able to think about is to "find" its faces, then to triangulate them. The problem is, to find (and define) these faces, I need a "cyclic ordering" of neighbors lists, and I don't know how to do this in an algorithm.
Could you help me on this, please ?
Edit : To make things very clear since the question seems hard to understand, I need to build a triangulation in order to make a Tutte embedding. Therefore, it is out of the question to use another embedding algorithm to define the triangulation.
 A: As other have mentioned, if your graph is not $3$-connected, then it can have more than one embedding in the plane, and hence its 'faces' are not well-defined.  
On the other hand, if you only want to find one planar embedding, then there are many planarity testing algorithms that actually output a planar embedding (if it exists).  One of the latest is this algorithm of Boyer and Myrvold which constructs a planar embedding in linear time based on the so-called edge addition method.  This method is probably the best for the application you have in mind, since you want to triangulate the graph anyway.  
A: You are asking for a planar embedding. As other people mentioned, it isn't generally unique except for 3-connected graphs (and even then there is the mirror image). There are several algorithms but they are either slow or hard to implement correctly, so it is best to go for an existing tested implementation.  There is one in Sage. There is also one in my package nauty that was implemented by Paulette Lieby for Magma.
A: With only a list of neighbors for each node, there is not a unique embedding
of the graph into the plane.

                


Maybe by "no coordinates or anything" you mean that you have the cyclic ordering
of the neighbors around each node?
Then see the earlier MO question: "Find all faces in a graph from list of edges."
As explained there, you need your graph
to be 3-vertex-connected to embed uniquely on the sphere.
Once on the sphere, you have your choice of which face to make the outer face
in a corresponding planar embedding.
