ABSTRACT
A graph G is planar if it can be drawn in the plane such that no two edges intersect, except at a common endpoint. The vertices of G are represented as points of the plane, and each edge of G is drawn as a continuous curve connecting the endpoints of the edge. For example, Figure 14.1 shows a planar graph (the cube), and a planar
drawing of the same graph. Although the cube is planar, the drawing on the left is not
a planar drawing. These drawings both have straight lines representing the edges, but
any continuous curve can be used to represent the edges. We shall often find it more
convenient to represent the vertices in planar drawings as circles rather than points,
but this is just a drawing convenience.
