chapter  10
36 Pages

Planar Graphs

Of the methods we have described to represent a graph G, probably the most common and the most useful for determining whether G possesses particular properties of interest is that of presenting G by means of a drawing. There are occasions when the edges in a diagram may cross and other occasions when the edges in a diagram do not cross. If some pairs of edges in a diagram of a graph cross, then it may be that there are other drawings of this same graph when no edges cross – or perhaps this is not possible. It is the class of graphs that can be drawn in the plane without their edges crossing that will be of interest to us in this chapter. We will see that a result of Euler plays a central role in this study.