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 12.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.
