Planar Graph

Published On :2022-04-04 12:25:00

 Planarity:

Definition: A graph is planar if it can be drawn in the plane with no crossing edges.

Otherwise, it is nonplanar.

Ex: 

Ex: Alll trees are planar graphs. 

(To show that, one can draw a tree rooted at one of its vertices or use induction to show that a tree is planar)

Definition: A plane graph is a graph that is drawn in the plane without edge crossing.

PHOTO

This is not a plane graph but it is a planar graph.

PHOTO

Defintion: The crossing number of a graph G is the smallest number of edge crossings of a plane drawing of the graph ( when the graph is drawn in the plane )

Remark: Cycles are planar.

Ex: Show that ..... is not planar?

SOL: Consider the graph .... observe that the ,, & ,, are adjacent to both ,, & ,, .This forms a cycle .C. that splits the plane into two regions ,, & ,, as shown.

PHOTO 

The vertex ,, is either in ,, or ,, . If ,, is in R,, , then R, is divided into two regions ,,, &,,, as shown.

PHOTO

We show that there is no way to place the final vertex ,, without crossing. 

If ,, is in R, , then the edge between ,, &,, can't be drawn without crossing.

If ,, is in ,,, , then the edge between ,, & ,, can't be drawn without crossing. If ,, is in ,,, , then the edge between ,, and ,, can't be drawn without crossing.

SIMILARLY, if ,, is in R,, .

According to the proof of the fact that ,,, is not planar, we get the crossing number of ,,, equals 1.