let’t start with the definition of the planar graph, a planar graph is a graph that can be embedded in the plane. To make this simple, a planar graph is a graph that you can draw on a paper in such a way that no edges cross each other. The Faces of a planar graph are the different areas that the graph makes on the 2D plane (your paper).
obviously the first graphs is a planar graphs, also the second graph is a planar graphs (why?). We can draw the second graph as shown on right to illustrate planarity.
Faces of a Graph
Graph 1 has 2 faces numbered with 1, 2, while graph 2 has 3 faces 1, 2, ans 3. The problem we are facing is how to count the number of faces in a planar graph. We have 2 approaches; the first using Euler’s formula. The second approach is by using disjoint sets. I was trying to solve uva 10178 – Count the Faces, the first soluion is what came to my mind is using Euler’s formula then i found another solution on The blue path using disjoint sets, in addition to the first solution.
Using Euler’s Formula
Euler’s formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and f is the number of faces (regions bounded by edges, including the outer, infinitely large region), then
v − e + f = 2.
easy as a piece of cake, yet it states that the graph must be connected, what happens if the graph is not connected. Utilizing the divide an conquer paradigm we can divide the graph into n component each component is a connected component, then we apply Euler’s formula on the n component and add the result. That’s right but we still missing something.
faces of the red component = 2 and faces of the green component = 2, the total # faces = 2+2 = 4. We are counting the outer face with every component. To fix this simply the eqn becomes ∑ (#faces of every component) – n + 1. Let’s verify this example first component; f = 2-V+E, f = 2-3+3 = 2. Second component f = 2-4+4 = 2. Total #faces = (2+2) – 2 +1 = 3. to code this we can use BFS or DFS to obtain the #edges and the #nodes in every component. you can find the implementation here.
Using Disjoint Sets
Building this graph, starting with 0 edges we have 1 face (outer face). Add edges AB, BF, FE still we have 1 face. At the moment we add AE we complete a cycle increasing the #faces to 2. By the same manner adding the edges BC and CD increase the number of faces. The question is how can we use disjoint sets to implement this ? the answer is very easy, for every edge if the edge is connecting 2 nodes that are on the same set increment #faces.
if(isSameSet(e.first, e.second)) faces++; unionSets(e.first, e.second);
2.The blue path blog.
3.Illustrations using graph creator.