# Cheeger constant and planarity of a graph

**URL:** <https://igraph.discourse.group/t/cheeger-constant-and-planarity-of-a-graph/814>\
**Category:** Usage\
**Tags:** Python\
**Created:** [12 August 2021 15:14 UTC](https://igraph.discourse.group/t/cheeger-constant-and-planarity-of-a-graph/814 "2021-08-12T15:14:31Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![etiennebonnafoux](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/etiennebonnafoux/32/532_2.png) [@etiennebonnafoux](https://igraph.discourse.group/u/etiennebonnafoux)\
**Post date:** [12 August 2021 15:14 UTC](https://igraph.discourse.group/t/cheeger-constant-and-planarity-of-a-graph/814/1 "2021-08-12T15:14:31Z")

</div>

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](https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)) ) 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,

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [12 August 2021 16:54 UTC](https://igraph.discourse.group/t/cheeger-constant-and-planarity-of-a-graph/814/2 "2021-08-12T16:54:56Z")

</div>

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:

> <https://github.com/igraph/igraph/issues/929>
>
> It would be nice to have a function to test planarity, and another one to find a… witness (Kuratowski subdivision) of non-planarity otherwise.

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](https://github.com/igraph/igraph/issues/new/choose) for feature requests that you can follow.

* * *

> [@etiennebonnafoux](#):
>
> If I code them should I push them to the GitHub repo ?

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](https://github.com/igraph/igraph/issues/1803#issuecomment-895973291). 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](https://github.com/igraph/igraph/wiki)

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [12 August 2021 17:11 UTC](https://igraph.discourse.group/t/cheeger-constant-and-planarity-of-a-graph/814/3 "2021-08-12T17:11:00Z")

</div>

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](https://lemon.cs.elte.hu/trac/lemon). It would be great to implement it in the igraph C core, but this is not the most trivial algorithm to deal with …

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [15 August 2021 15:54 UTC](https://igraph.discourse.group/t/cheeger-constant-and-planarity-of-a-graph/814/4 "2021-08-15T15:54:01Z")

</div>

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

> <https://github.com/igraph/igraph/issues/1807>
>
> \*\*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