Planarity
W. D. Wallis · Birkhäuser Boston eBooks · 2000
The two diagrams in Figure 8.1 represent the same graph, a K 4 with vertices a , b , c and d . As diagrams they are quite different: in the left-hand version, the edges ac and bd cross; in the right-hand version there are no crossings. We shall refer to the two diagrams as different representations of the graph in the plane. The crossing number of a representation is the number of different pairs of edges that cross; the crossing number v ( G ) of a graph G is the minimum number of crossings in any representation of G. A representation is called planar if it contains no crossings, and a planar graph is a graph that has a planar representation. In other words, a planar graph G is one for which v ( G ) = 0. Figure 8.1 shows that v ( K 4 ) = 0. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.