MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a dense unlabeled graph ( each vertex has got at least 4 incident edges ).

Number of vertices (V) of the graph is always a perfect square.

I want to find all the meshes of $\sqrt{v} {x} \sqrt{v}$ in it.

Are there any known algorithms to accomplish this?

Any help is appreciated.


share|cite|improve this question
up vote 2 down vote accepted

There could easily be an exponential number of meshes (e.g. let your graph be complete). And it's NP-complete to find even one of them (a graph G has a Hamiltonian path if and only the Cartesian product of G with a path contains a mesh).

So, yes, there are algorithms — you can just do a brute force search over all permutations of the vertices, for instance — but not polynomial algorithms.

share|cite|improve this answer
Oh no! I have 256 nodes i.e. 256! possibilities. Yet another attempt to make a million dollars failed. Thanks! :D – Pratik Deoghare Jul 14 '10 at 21:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.