1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Tony Huynh
    Commented May 13, 2016 at 19:07
  • $\begingroup$ 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. $\endgroup$
    – Yann Bouteiller
    Commented May 13, 2016 at 19:13
  • 3
    $\begingroup$ Who are "they"? $\endgroup$
    – Robert Israel
    Commented May 14, 2016 at 0:12

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$
    – Yann Bouteiller
    Commented May 13, 2016 at 18:45
  • $\begingroup$ Once you have an embedding, it is easy to triangulate the graph. $\endgroup$
    – Tony Huynh
    Commented May 13, 2016 at 18:47
  • $\begingroup$ Yes but it would be quite stupid because I have to deduce the embedding from the triangulation, and not the triangulation from the embedding. $\endgroup$
    – Yann Bouteiller
    Commented May 13, 2016 at 18:48
  • $\begingroup$ (a triangulation defines one only embedding, an embedding can lead to several triangulations) $\endgroup$
    – Yann Bouteiller
    Commented May 13, 2016 at 18:52
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yann Bouteiller
    Commented May 14, 2016 at 15:13
  • $\begingroup$ @Yann : It is the same thing. It is easily to go from faces to cyclic orders and back. $\endgroup$
    – Brendan McKay
    Commented May 15, 2016 at 0:31
0
$\begingroup$

With only a list of neighbors for each node, there is not a unique embedding of the graph into the plane.

                 TwoK4Embed
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.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ 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). $\endgroup$
    – Tony Huynh
    Commented May 13, 2016 at 17:57
  • 1
    $\begingroup$ @TonyHuynh: Good point. But I think the issue is clear so I won't bother to draw another example. $\endgroup$
    – Joseph O'Rourke
    Commented May 13, 2016 at 18:16
  • $\begingroup$ 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. $\endgroup$
    – Yann Bouteiller
    Commented May 13, 2016 at 18:23
  • $\begingroup$ @YannBouteiller: then you cannot win! The ordering is an independent ingredient. $\endgroup$
    – Loïc Teyssier
    Commented May 13, 2016 at 18:31
  • $\begingroup$ Then, how do you create this independent ingredient... $\endgroup$
    – Yann Bouteiller
    Commented May 13, 2016 at 18:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .