Computing the Cheeger constant: feasible for which classes? Computing the Cheeger constant of a graph, also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated.  I am interested to learn if exact polynomial algorithms
are known for special classes of graphs.
For example, is it still NP-complete for regular graphs?
For distance-regular graphs?
(I have not studied the existing NP-completeness proofs to examine their assumptions.)
Literature pointers appreciated&mdash;thanks!
Notice that approximating sparsest cut to within $\alpha$ gives a $2\alpha$ approximation for the Cheeger constant as defined. Here are some papers that give constant approximation algorithms for sparsest cut in restricted graphs:


Bounded genus: http://dl.acm.org/citation.cfm?id=1873619
Bounded treewidth: http://arxiv.org/abs/1006.3970


Furthermore, http://arxiv.org/abs/1006.3970v2 proves that sparsest cut is NP-hard for graphs with pathwidth 2, and has quite a few more references to approximating sparsest cut on restricted instances.

I would assume that for all classes of graphs mentioned in the paper, no exact algorithms are known (as they're interested in approximations). In particular, if sparsest cut is NP-hard for graphs with pathwidth 2, it's also NP-hard for graphs of treewidth 2, and cutwidth 2. I suppose that doesn't give quite a lot of room.. maybe there is another better parameterization for sparsest cut.

I am pretty sure that sparsest cut is NP-hard on regular graphs but can't find a reference.



Per noticed that I wasn't careful when I looked at the papers above. The hardness result is for nonuniform sparsest cut. Computing uniform sparsest cut or the Cheeger constant is easy on trees (WLOG the optimal cut separates a subtree). With a little more work that gives a dynamic programming algorithm for computing the Cheeger constant on bounded treewidth graphs. 

Table 1 in paper 2 above also mentions a result that gives a constant approximation for graphs with an excluded minor.

For bounded genus graphs, the best that seems to be known is a constant approximation (paper 1 above gives $O(\sqrt{\log g})$ where $g$ is the genus.