Chapter 2   The width of embeddings

 In their work on graph minors Robertson and Seymour [RS88] introduced the face-width (or representativity) as a measure of how dense a graph is embedded on a surface. The face-width of a graph embedded in S is the smallest number k such that S contains a noncontractible closed curve that intersects the graph in k points. A related concept is the edge-width of an embedded graph G defined as the length of a shortest noncontractible cycle in G. Robertson and Seymour proved that any infinite sequence of graphs embedded in a fixed surface S with increasing face-width can serve as a generic class of graphs on S in the sense that every embedding in S is a surface minor of one of these embeddings. We treat this aspect of face-width in Section 5.9. Robertson and Vitray developed the basic theory of face-width in [RV90]. They showed that embeddings of large face-width are minimum genus embeddings and that they share many important properties with planar embeddings. The same phenomenon was discovered independently by Thomassen [Th90b] under the condition that the edge-width is greater than the maximum length of a facial walk.

In this chapter we discuss embedding results involving width. In the first part we study edge-width by following [Th90b] (extending the results from orientable to arbitrary embeddings). Particular attention is given to the so called LEW-embeddings whose edge-width is larger than the maximum length of a facial walk. In Section 5.4 we show that for every surface and any integer k there are only finitely many minimal triangulations of edge-width k. The rest of the chapter is devoted to face-width. In Section 5.5 the basic theory is developed. Section 5.6 treats minor minimal embeddings of a given face-width. Section 5.10 contains results about uniqueness and flexibility of embeddings of graphs. The remaining sections contain further results on embedded graphs of large face-width. For some other aspects and additional references on face-width we refer to Robertson and Vitray [RV90] and Mohar [Mo97c].