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.