Suppose $2n$ points along the edge of a Möbius strip are labeled by some given permutation of $[1,1,2,2,\dots,n,n]$. Is there a criterion or algorithm to determine whether we can draw $n$ non-intersecting paths on the strip so that the endpoints of the $i$th path are the points labeled $i$?
This is the same as this question but starting with a Möbius strip instead of a sphere with holes. The problem seems interesting on other surfaces, too. On an orientable surface of genus $g$ with a single hole, my intuition is that the number of allowable occurrences of subsequences of the form $i,j,i,j$ (going around the hole boundary) is bounded by some increasing function of $g$ (and if there are multiple individually-solvable holes, they can still obstruct each other, unlike on the sphere). The situation is different on the Möbius strip (which we can view as the projective plane with a hole), since it allows $[1,\dots,n,1,\dots,n]$ for arbitrary $n$. However, 123132 is not allowed. Is the absence of $ijkikj$ a sufficient condition?
There is an algorithm, like this.
The input is a cyclic sequence $(i_1,i_2,...,i_{2n-1},i_{2n})$ in which each of $1,2,...,n$ appears exactly twice.
Now do a loop: as long as there exist two cyclically consecutive entries that are equal, i.e. $i_{k-1} = i_k$ for some $k$ modulo $2n$, remove those two entries, and continue the loop. Removal of those two entries corresponds to connecting the two points by a path $\alpha$ with those two endpoints, such that if we let $\beta$ denote the boundary path with those two endpoints that is disjoint from all the other points then $\alpha \cup \beta$ bounds a disc.
Once the loop is all over, look at the remaining cyclic sequence, which we rewrite in the form $(i_1,...,i_{2m})$ for some $0 \le m \le n$. Now ask the question: is this sequence a concatenation of two copies of a permutation of $m$ elements? In other words, is it in the form $(j_1,...,j_m,j_1,...,j_m)$ such that $j_1,...,j_m$ is a permutation of a subset of $\{1,...,n\}$? If so, then the algorithm is done with the answer "Yes, the paths can be drawn". If not, the algorithm is done with the answer "No, the paths cannot be drawn".