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


Computational Geometry

It’s my first tutorial so if u found any mistakes feel free to post it in a comment :D. Also some code may not seem clear i’ll try to post more tutorials later 😀 .

Point On Segment

First line is to check if the segment ab is a point, if so check that p also the same point.

then get the cross product of ab and ap , if the cross product equals 0 then the 3 points are co-linear, that’s the first condition, yet point p may by on the same line of ab but doesn’t lie on ab.

we check this case by getting the angle between vectors ab and ap  (dot(ab,ap)) then the angle between vectors ba and bp (dot(ba,bp)).

Recall : the dot product of 2 vectors > 0 the angle θ between these 2 vectors is acute.

we used ” > -EPS ” to evade the errors in the double representation.

typedef int type;
typedef complex<type> Point;

#define X real()
#define Y imag()
#define length(p)  (hypot( (p).X , (p).Y ))
#define rec(a,b)   ((b)-(a))
#define dot(a,b)   (((conj(a))*(b)).real())
#define cross(a,b) (((conj(a))*(b)).imag())
bool pointOnSegment(const Point &a, const Point &b,const Point&p){
    if (length(rec(a,b)) < EPS) return length(rec(a,p)) < EPS ;//case that 3 points are tha same
    return fabs(cross(rec(a,b),rec(a,p))) < EPS //3 points are colinear
            && dot(rec(a,b),rec(a,p)) > -EPS && dot(rec(b,a),rec(b,p)) > -EPS;//between a,b

Intersecting Segments

photo taken from saipanyam.net

bool intersectSegment(const Point &a, const Point &b,const Point&p,const Point &q){
    type d1 = cross(p-a,b-a);
    type d2 = cross(q-a,b-a);
    type d3 = cross(a-p,q-p);
    type d4 = cross(b-p,q-p);
    if(d1*d2 <-EPS  && d3*d4 <-EPS) return true;//d1,d2 have different directions and d3,d4 have different directions
    else if (d1<EPS && pointOnSegment(a,b,p)) return true;//p is colinear with ab
    else if (d2<EPS && pointOnSegment(a,b,q)) return true;//q is colinear with ab
    else if (d3<EPS && pointOnSegment(p,q,a)) return true;//a is colinear with pq
    else if (d4<EPS && pointOnSegment(p,q,b)) return true;//b is colinear with pq
    else return false;