Include graph embedding method from C code

[MeikeWeiss]

Gunnar Brinkmann wrote some really nice C code for computing all orientable non-isomorphic embeddings of given graphs and given genus (or computing the minimal genus). The C code based on this paper (https://arxiv.org/abs/2408.16512) is attached.

The method takes as input a file where graphs are stored as multi_code (I have also some methods from him converting for example multi_code to e.g. Graph6 format) and either an m if all the minimal orientable embeddings should be computed, or an integer which defines the genus on which the graphs should be embedded and all the corresponding embeddings are computed. It would be nice to also have both options in GAP. The output embeddings can be stored as a .pl file including planar code, which can be converted to readable information by the method provided from planarlese2 containing the rotation system.

I can offer some tests with the help of 3-connected cubic graph which are attached for 20 vertices in g6 format. All of these have as minimal genus 0 and only one embedding on the plane. In sum there should be 55885 embeddings on genus 1 of these graphs where the facial walks are cycles (can be tested by FacialWalks).

PS: He also wrote code that computes only one embedding and is more efficient, if someone is interested in this. I hope that I made no mistakes by renaming some variables from German to English.

graphEmbedding.zip

[wilfwilson]

Thanks for this @MeikeWeiss, that's a nice idea. There are about 3,500 lines of code in the attached files.

Do you propose we translate some or all of the code into GAP code, or just incorporate it into the Digraphs package as C code?

[james-d-mitchell]

I think the latter might be preferable, but not sure what @MeikeWeiss intended

[MeikeWeiss]

Yes, I agree with @james-d-mitchell