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