Graph Concepts

Planarity and crossing numbers

A graph is planar if it can be drawn so that none of its edges intersect except at vertices. A graph that is not planar is called a nonplanar graph. planar graph

different pictures of a planar graph When a planar graph is drawn with edges crossing, it is still a planar graph. The graph on the left is planar because it can be redrawn as on the right.

In some contexts, a planar graph is called a map because of the resemblance that it bears to a geographic map. The regions of such a map are the areas outlined by the vertices and edges, the areas that would correspond to the countries on a map.

According to Euler's theorem, if R represents the number of regions in a planar graph (including the outside), if E represents the number of edges, and if V represents the number of vertices, then R – E + V = 2. This theorem is used to prove that a graph is not planar if 3V – E < 6.

The crossing number of a graph is the smallest number of intersections needed to draw the graph. So the crossing number of any planar graph is 0.

k 5 K₅ is a nonplanar graph with crossing number 1.