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. 


Thanks! 



Algorithm for finding mesh subgraphs?
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.


