Post Undeleted by aelguindy occurred Nov 2 '16 at 23:03 3 added 141 characters in body edited Nov 2 '16 at 23:03 aelguindy 1,5071010 silver badges1616 bronze badges Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component. 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')$$. Decompose your graph into biconnected components. Since only a biconnected component can border faces. This can be done in linear time. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component. Pick the component with the largest number of faces and find the cycle bordering that component. This is Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component. 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')$$. 2 added 91 characters in body edited Nov 2 '16 at 22:53 aelguindy 1,5071010 silver badges1616 bronze badges The number you are looking for is given by the formula $$F = E' - V' + 2$$, see Euler's characteristic. For a quick explanation. The graph $$G$$ (when drawn as a grid) is clearly planar. If you take the subgraph $$H$$ (with the same drawing), the number of simple cycles corresponds to the number of faces of the polygons drawn by this graph. Decompose your graph into biconnected components. Since only a biconnected component can border faces. This can be done in linear time. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component. Pick the component with the largest number of faces and find the cycle bordering that component. This is The number you are looking for is given by the formula $$F = E' - V' + 2$$, see Euler's characteristic. For a quick explanation. The graph $$G$$ (when drawn as a grid) is clearly planar. If you take the subgraph $$H$$ (with the same drawing), the number of simple cycles corresponds to the number of faces of the polygons drawn by this graph. Decompose your graph into biconnected components. Since only a biconnected component can border faces. This can be done in linear time. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component. Pick the component with the largest number of faces and find the cycle bordering that component. This is Post Deleted by aelguindy occurred Nov 2 '16 at 22:39 1 answered Nov 2 '16 at 22:38 aelguindy 1,5071010 silver badges1616 bronze badges The number you are looking for is given by the formula $$F = E' - V' + 2$$, see Euler's characteristic. For a quick explanation. The graph $$G$$ (when drawn as a grid) is clearly planar. If you take the subgraph $$H$$ (with the same drawing), the number of simple cycles corresponds to the number of faces of the polygons drawn by this graph.