Chapter 6 Embedding extensions and obstructions
The results presented in Chapter 2 (Sections 2.3 - 2.7) demonstrate the importance of Kuratowski's Theorem for the study of planar graphs. In the 1930's Erdos and Konig [Koe36] raised the question if for each surface S, there is a finite list Forb(S) of graphs such that exclusion of these graphs and all their subdivisions as subgraphs characterizes the graphs embeddable in S (not necessarily 2-cell embeddable). The first results in this direction were obtained in the 1970's when Glover and Huneke settled the problem for the projective plane [GH78] by showing that Forb(N1) is finite. Glover, Huneke, and Wang [GHW79] exhibited a list of 103 graphs in Forb(N1), and Archdeacon [Ar80, Ar81] showed that this list is complete. The finiteness of Forb(N1) is proved and the list is presented in Section 6.5.Robertson and Seymour [RS90b, RS84a, RS85] settled the general conjecture by proving that Forb(S) is finite for each surface S. This result is an important step towards a proof of a more general statement, that has become known as Wagner's conjecture, which states that every family of graphs that is closed under the operation of deleting or contracting edges can be characterized by excluding a finite set of graphs as minors. An independent proof of the finiteness of Forb(S) for nonorientable surfaces S was obtained by Archdeacon and Huneke [ArH89].
The original proof of Robertson and Seymour [RS90b] of the finiteness of Forb(S) is existential whereas Seymour [Se94p] obtained a constructive proof by using graph minors and tree-width techniques which also gives an explicit upper bound for the number of vertices of the graphs in Forb(S). An independent constructive proof (which leads to very efficient embedding algorithms; cf. Theorem 6.6.3) was found by Mohar [Mo96, Mo99]. A much shorter proof was recently found by Thomassen [Th97c]. We shall present it in the next chapter. However, that proof depends on two difficult results of Robertson and Seymour, namely the excluded grid theorem [RS86b] and the result that the graphs of bounded tree-width are well-quasi-ordered with respect to the minor relation. A simple proof of the former was obtained recently by Diestel, Jensen, Gorbunov, and Thomassen [DJGT98p] and is also included in Chapter 7.
The most natural approach (used, for example, in [ArH89] and in [Mo96, Mo99]) to study graphs in Forb(S) is by induction on the (Euler) genus of S. The basic idea is the following. Suppose for simplicity that S is orientable and that S=Sg. Every graph G in Forb(S) contains a subdivision K of some graph K_0 in Forb(Sg-1). By the induction hypothesis, K does not have too many vertices of degree different from 2 and hence K admits only a bounded number of embeddings in S (where the bound depends on g only). Since G belongs to Forb(S), no embedding of K in S can be extended to an embedding of the whole graph. Therefore, G is just the union of K and (minimal) subgraphs of K-bridges (defined in Section 6.2) - called obstructions - whose presence in G "obstructs" embedding extensions. If the number of K-bridges forming an obstruction is large, K can be replaced by another subdivision of K_0 in G such that we obtain a smaller obstruction. This idea leads to the study of the structure of obstructions for general embedding extension problems that ask whether a given embedding of a subgraph can be extended to an embedding of the whole graph in the same surface. Moreover, in such embedding extension problems we may allow only some of the possible embeddings of K-bridges.
In this chapter we study obstructions for embedding extensions and we demonstrate in Section 6.5 how they can be applied to show that Forb(N1) is finite. In the last section we briefly discuss some results on the minimal forbidden subgraphs for other surfaces.