SKEDSOFT
DETECTION OF PLANARITY OF A GRAPH : If a given graph G is planar or non planar is an important problem. We must have some simple and efficient criterion. We take the following simplifying steps :
Elementary Reduction :
Step 1 : Since a disconnected graph is planar if and only if each of its components is planar, we need consider only one component at a time. Also, a separable graph is planar if and only if each of its blocks is planar. Therefore, for the given arbitrary graph G, determine the set.
G = {G1, G2, ...... Gk}
where each Gi is a non separable block of G.
Then we have to test each Gi for planarity.
Step 2 : Since addition or removal of self-loops does not affect planarity, remove all self-loops.
Step 3 : Since parallel edges also do not affect planarity, eliminate edges in parallel by removing all but one edge between every pair of vertices.
Step 4 : Elimination of a vertex of degree two by merging two edges in series does not affect planarity. Therefore, eliminate all edges in series. Repeated application of step 3 and 4 will usually reduce a graph drastically.
For example, Figure (2.46) illustrates the series-parallel reduction of the graph of Figure (2.45). Let the non separable connected graph Gi be reduced to a new graph Hi after the repeated application of step 3 and 4. What will graph Hi look like ? Graph Hi is
- A single edge, or
- A complete graph of four vertices, or
- A non separable, simple graph with n ≥ 5 and e ≥ 7.
