chapter  7
Graph Embeddings
Pages 42

While only planar graphs can be embedded in the plane, there is a host of common and increasingly complex surfaces on which a nonplanar graphGmight possibly be embedded. Determining the simplest of these surfaces on which G can be embedded gives an indication of how close G is to being planar. We will see that the embeddings of interest are those called 2-cell embeddings and discuss the possible surfaces on which a given graph has such an embedding.