Cheeger constant and planarity of a graph

etiennebonnafoux · 12 August 2021 15:14

Hello,

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,

szhorvat · 12 August 2021 16:54

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

szhorvat · 12 August 2021 17:11

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 …

szhorvat · 15 August 2021 15:54

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

github.com/igraph/igraph

Cheeger Constant

opened 02:06PM - 13 Aug 21 UTC

etiennebonnafoux

wishlist

**Description** The Cheeger constant is a measure of a easy it is to cut a gr…aph in two part. More formally for a graph G=(E,V), it is <img src="https://latex.codecogs.com/svg.image?\underset{A&space;\subset&space;V,&space;0&space;\leq&space;|A|&space;\leq&space;|V|/2}{\inf}&space;\frac{|&space;\delta&space;A|}{|A|}" title="\underset{A \subset V, 0 \leq |A| \leq |V|/2}{\inf} \frac{| \delta A|}{|A|}" /> where |.| is the cardinality of a set and <img src="https://latex.codecogs.com/svg.image?\delta&space;A&space;=&space;\{&space;(x,y)&space;\in&space;E,&space;x&space;\in&space;A&space;,&space;y&space;\notin&space;A&space;\}" title="\delta A = \{ (x,y) \in E, x \in A , y \notin A \}" /> . It is linked by a to the second eigenvalue of the laplacian of the graph. **Use cases for the feature** This constant is used in one of the definition of a expander family of graph, namely a family of graph is expander if the number of vertices go to infinity and the Cheeger constant is uniformly bound away from zero. It has practical uses to create robust network (the deficiency of a vertices do not impact to much the connectedness of the graph). **Computation** That's the tricky part. Computing this constant is a NP-problem. The naive way is two compute for every subset the quotient of the boundary by the cardinality which is <img src="https://latex.codecogs.com/svg.image?O(2^{|V|-1})" title="O(2^{|V|-1})" />. Some author have solution for some class of graph, see [[2]](https://dl.acm.org/doi/10.1145/167088.167284) for planar graph. Otherwise only approximation algorithm exist for bounded treewidth [[3]](https://arxiv.org/abs/1006.3970) and for bounded genus [[4]](https://dl.acm.org/doi/10.5555/1873601.1873619). See this thread for a discussion about it [[5]](https://cstheory.stackexchange.com/questions/8615/computing-the-cheeger-constant-feasible-for-which-classes) . I think we should maybe make two feature one give exact value, one quicker give an approximate value. Moreover it can be also interesting to not only give the Cheeger constant but also the set A which give the minimum in the definition. **References** [1] https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory) [2] https://dl.acm.org/doi/10.1145/167088.167284 [3] https://arxiv.org/abs/1006.3970 [4] https://dl.acm.org/doi/10.5555/1873601.1873619 [5] https://cstheory.stackexchange.com/questions/8615/computing-the-cheeger-constant-feasible-for-which-classes

Topic		Replies	Views
Welcome to the igraph discussion forum!	1	799	28 January 2020
C/igraph 0.10.2 Announcements C	0	207	16 October 2022
C/igraph 0.9.0 Announcements C	0	711	16 February 2021
C/igraph 0.10.0 Announcements C	5	340	11 September 2022
C/igraph 0.10.7 Announcements C	0	184	4 September 2023

Cheeger constant and planarity of a graph

Related Topics