Chapter 6 **Embedding extensions and obstructions**

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=**S**_{g}. Every graph G in Forb(S)
contains a subdivision K of some graph K_0 in
Forb(**S**_{g-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(**N**_{1}) is finite.
In the last section we briefly discuss some results on
the minimal forbidden subgraphs for other surfaces.