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.

• If all you care about is finding a Tutte embedding, then there are direct algorithms to do this. For example, see math.uwaterloo.ca/~jfgeelen/Publications/tutte.pdf – Tony Huynh May 13 '16 at 19:07
• Yes, the problem is, they ask for a triangulation. (Or at least a 3-connected graph even though I don't know yet how this helps at all for Tutte embeddings). But thank you for the paper, I'll read it. – Yann Bouteiller May 13 '16 at 19:13
• Who are "they"? – Robert Israel May 14 '16 at 0:12

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.

• I know, but that is not what I want to do. I want to triangulate the graph (any triangulation will do, it only has to keep the planarity of the graph) – Yann Bouteiller May 13 '16 at 18:45
• Once you have an embedding, it is easy to triangulate the graph. – Tony Huynh May 13 '16 at 18:47
• Yes but it would be quite stupid because I have to deduce the embedding from the triangulation, and not the triangulation from the embedding. – Yann Bouteiller May 13 '16 at 18:48
• (a triangulation defines one only embedding, an embedding can lead to several triangulations) – Yann Bouteiller May 13 '16 at 18:52

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.

• Well, actually I am only asking for a cyclic ordering (or a way to triangulate) but it might be more or less the same thing indeed. – Yann Bouteiller May 14 '16 at 15:13
• @Yann : It is the same thing. It is easily to go from faces to cyclic orders and back. – Brendan McKay May 15 '16 at 0:31

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.

• Perhaps the example in the picture is not the best? Those are the same embedding on the sphere. There are graphs with genuinely different embeddings (not related by stereographic projection). – Tony Huynh May 13 '16 at 17:57
• @TonyHuynh: Good point. But I think the issue is clear so I won't bother to draw another example. – Joseph O'Rourke May 13 '16 at 18:16
• No, I mean that I DO NOT have the cyclic ordering of the neighbors around each node (nor anything else), my question actually is "how do you define this ordering in an algorithm", if it makes things clearer. – Yann Bouteiller May 13 '16 at 18:23
• @YannBouteiller: then you cannot win! The ordering is an independent ingredient. – Loïc Teyssier May 13 '16 at 18:31
• Then, how do you create this independent ingredient... – Yann Bouteiller May 13 '16 at 18:33