ABSTRACT

A graph is planar if it is possible to draw it on a plane so that no edges intersect, except at endpoints. Such a drawing is called a planar embedding.

Not all graphs are planar: Figure 32.1 gives examples of two graphs that are not planar. They are known as K5 , the complete graph on five vertices, and K3,3, the complete bipartite graph on two sets of size 3. No matter what kind of convoluted curves are chosen to represent the edges, the attempt to embed them always fails when the last of the edges cannot be inserted without crossing over some other edge, as illustrated in the figure.