Output of PlanarEmbedding

[MeikeWeiss]

The planar embedding method returns only a minimal rotation system, i.e. for each vertex the method returns only a list with entries of smaller vertices. Such a list is not easy to work with. It must be possible to extend this list in such a way that we get a list containing for each vertex all neighbours in such a order that it defines a planar embedding.

Here are some examples of how the actual output and how it would be easier to work with the computed planar embedding:

PlanarEmbedding(CompleteDigraph(4));
[ [ 2, 4, 3 ], [ 3, 4 ], [ 4 ], [  ] ] 
 ------> [ [ 2, 4, 3 ], [ 3, 4, 1 ], [ 4, 2, 1], [ 1, 2, 3 ] ] 

Cubical Graph:

g:=DigraphByEdges([ [ 1, 3 ], [ 3, 1 ], [ 1, 7 ], [ 7, 1 ], [ 5, 7 ], [ 7, 5 ], [ 3, 5 ], [ 5, 3 ], [ 1, 4 ], [ 4, 1 ], [ 2, 3 ], [ 3, 2 ], [ 2, 4 ],[ 4, 2 ], [ 6, 7 ], [ 7, 6 ], [ 4, 6 ], [ 6, 4 ], [ 5, 8 ], [ 8, 5 ], [ 6, 8 ], [ 8, 6 ], [ 2, 8 ], [ 8, 2 ] ]);
PlanarEmbedding(g);
[ [ 3, 7, 4 ], [ 4, 8, 3 ], [ 5 ], [ 6 ], [ 8, 7 ], [ 7, 8 ], [  ], [  ] ]
------> [ [ 3, 7, 4 ], [ 4, 8, 3 ], [ 5, 1, 2 ], [ 6, 2, 1 ], [ 8, 7, 3 ], [ 7, 8, 4], [ 1, 5, 6], [ 2, 6, 5] ]

Note that the rotation system for a planar graph is not unique so the output could differ.

[james-d-mitchell]

Thanks @MeikeWeiss I'll think about this, and see if we can't offer what you suggest?

[james-d-mitchell]

This was hopefully resolved by #696, @MeikeWeiss, any chance you can confirm this?

[MeikeWeiss]

I wanted to test the method with some examples to confirm this, but I pulled the new version and now I get the error message:

Error, Variable: 'DIGRAPH_NRADJACENCIES' must have a value

I'm not sure what the problem is.

[Joseph-Edwards]

I wanted to test the method with some examples to confirm this, but I pulled the new version and now I get the error message:

Error, Variable: 'DIGRAPH_NRADJACENCIES' must have a value

I'm not sure what the problem is.

Argh that's annoying. Would you mind sharing the code that generated this error, and the full output from the error please?

[MeikeWeiss]

When I try to start GAP, the error appears immediately...

[james-d-mitchell]

@MeikeWeiss you probably just need to recompile Digraphs, then it should work!

[MeikeWeiss]

Oh wow:) Thank you!

I looked at some examples and there the output is correct! In the course of the next week I will probably incorporate the method into my embedding algorithm so that it can be tested intensively.