Projective plan and Möbius band obstructions (Q1385984)

Let \(S\) be a compact surface with possibly non-empty boundary \(\partial S\) and let \(G\) be a graph. Let \(K\) be a subgraph of \(G\) embedded in \(S\) such that \(\partial S\subseteq K\). An embedding extension of \(K\) to \(G\) is an embedding of \(G\) in \(S\) which coincides on \(K\) 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 Möbius band. In unit-cost RAM model linear time algorithms are presented that either find an embedding extension, or return a `nice' obstruction for the existence of extensions.