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. |
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} is a nonplanar graph with crossing number 1. |
Copyright © 1999-2000 SciMathMN