Faces of a planar graph

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

First, think about when do we add another face to the graph ? the answer is when we complete a cycle – recall from the definition of planar graph no edges cross – .

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);

to practice this problem solve uva 10178 – Count the Faces. Also you can check the solution of this problem by the 2 ways here.

References : 

1.Planar graph on wikipedia.

2.The blue path blog.

3.Illustrations using graph creator.

Advertisements

One thought on “Faces of a planar graph

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s