Projective plane and Mobius band obstructions

Let S be a compact surface with possibly non-empty boundary partial derivative S and let G be a graph. Let It be a subgraph of G embedded in S such that partial derivative S subset of or equal to K. An embedding 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 the existence of embedding extensions are classified in cases when S is the projective 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 extensions.