Post Undeleted by aelguindy
3 added 141 characters in body
source | link
  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')$.

  1. Decompose your graph into biconnected components. Since only a biconnected component can border faces. 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 is

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

2 added 91 characters in body
source | link

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.

  1. Decompose your graph into biconnected components. Since only a biconnected component can border faces. 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 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.

  1. Decompose your graph into biconnected components. Since only a biconnected component can border faces. 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 is

    Post Deleted by aelguindy
1
source | link

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.