Cheeger constant and planarity of a graph


I am looking for two (should I make two different topics ?) function in the library but I am not sure they exist.
One calculate the Cheeger constant of the graph ( Cheeger constant (graph theory) - Wikipedia ) and the second say if a graph is planar or not. Do the two preceding function already exist or should I code them by my-self ? If I code them should I push them to the GitHub repo ?
Thank you,

No, they are not implemented.

The issue for planarity testing is here, you may add your vote to it in the form of a comment or :+1: icon:

You can create a new issue (feature request) for the Cheeger constant. Ideally, include a definition of the concept, pointers to algorithms for computing it, and a description of its applications / usefulness, so that we can more easily prioritize it. There’s a template for feature requests that you can follow.

Contributions are of course very welcome!

If/when you plan to start working on this, please let us know in advance. It’s best if you can do the work in the open, in a draft PR, so we can help you with igraph-specific technical issues as you go. See also what I wrote here. I would suggest to start with an empty PR, and write down a clear plan for the implementation, including an explanation of the algorithm. It is possible (in fact likely) that none of the igraph developers will be familiar with the details of the algorithm, and it will be a huge help if we can learn the details together. In the past there were instances of PRs with no explanation, just code, and these are in fact more time consuming to review than implementing the same thing ourselves. So, don’t be shy to ask early and often, and to show incomplete work!

At this time new PRs should be based on the develop branch (i.e. not master).

You will find some helpful guides in the wiki: Home · igraph/igraph Wiki · GitHub

1 Like

For planarity testing, it would be excellent to compute not just a yes/no answer, but also a witness of non-planarity (Kuratowski obstruction) if the graph is not planar, and a combinatorial embedding if it is planar. Finally, it would be very useful to fully support non-simple graphs (multi-edges and self-loops).

IGraph/M, which serves as igraph’s Mathematica interface, does in fact have these features, but they are not provided by igraph’s C core. Instead, I borrowed them from LEMON. It would be great to implement it in the igraph C core, but this is not the most trivial algorithm to deal with …

1 Like

For completeness, here’s the newly opened feature request: