chapter  11
30 Pages

Nonplanar Graphs

We saw in Chapter 10 that if G is a maximal planar graph containing two nonadjacent vertices u and v, then the graph G + uv obtained by adding the edge uv is nonplanar. Although nonplanar, the graph G + uv is very close to being planar. We now look at various ways of measuring how close nonplanar graphs are to being planar.