PROJECTIVE PLANE AND MOBIUS BAND OBSTRUCTIONS

Let S be a compact surface with possibly non-empty boundary partial de rivative S and let G be a graph. Let It be a subgraph of G embedded il l S such that partial derivative S subset of or equal to K. An embeddi ng extension of K to G is an embedding of G in S which coincides on It with the given embedding of K. Minimal obstructions for tile existenc e of embedding extensions are classified ill cases when S is the proje ctive plane or the Mobius band (for several ''canonical'' choices of K ). Linear time algorithms are presented that either find all embedding extension, or return a ''nice'' obstruction for the existence of exte nsions.