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

Question

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! :-)

Answer 1

1. Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time.

2. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component.

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')$.