2-Restricted Extensions Of Partial Embeddings Of Graphs

Let K be a subgraph of G. Suppose that we have a 2-cell embedding of K in some surface and that for each K-bridge in G one or two simple embeddings in faces of K are prescribed. A linear time algorithm is presented that either finds an embedding of G extending the embedding of K in the same surface using only prescribed embeddings of K-bridges, or finds an obstruction which certifies that such an extension does not exist. It is described how the obtained obstructions can be transformed into minimal obstructions in linear time. The geometric and combinatorial structure of minimal obstructions is also analyzed. At the end we apply the above algorithm to solve general embedding extension problems where the embedding of K is a closed 2-cell embedding. 1 Introduction Let K 0 be a fixed graph together with a fixed 2-cell embedding in some (closed) surface. Let G be a graph containing a subgraph K homeomorphic to K 0 . The embedding of K 0 and the homeomorphism K ! K 0 determine a 2-cell em..