# Find a simple cycle in an undirected subgraph of a grid graph that encloses the most faces

Imagine a finite $n*n$ grid graph $G(V,E)$, much like a chessboard. Imagine further an undirected subgraph $H(V',E')$ of $G$. Let us call the squares of chessboard $G$ "faces". A DFS algorithm can detect a simple cycle in $H$ in linear time. However, such a search cannot efficiently find all simple cycles in $H$ as the number of cycles can grow exponentially (?) with the numer of vertices of $H$.

Remark: Since I'm referring to a square grid graph, we have maximum degree 4 for the vertices of $H$. Furthermore, $H$ does not have to be strongly connected. It does not have to have a "reasonable" data structure.

I wonder: What is the time complexity for finding the simple cycle, should it exist, that encloses (surrounds) the most faces? That simple cycle $C(V'',E'')$ is of course itself a subgraph of $H$.

Edit: I would like to add that the very same problem but with a directed graph is also of interest! :-)

3. Pick the component with the largest number of faces and find the cycle bordering that component. This can be done with a single line sweep, which is $O(V' \log V')$.