  In this article, we investigate short topological decompositions of
non-orientable surfaces and provide algorithms to compute them. Our main result
is a polynomial-time algorithm that for any graph embedded in a non-orientable
surface computes a canonical non-orientable system of loops so that any loop
from the canonical system intersects any edge of the graph in at most 30
points. The existence of such short canonical systems of loops was well known
in the orientable case and an open problem in the non-orientable case. Our
proof techniques combine recent work of Schaefer-\v{S}tefankovi\v{c} with ideas
coming from computational biology, specifically from the signed reversal
distance algorithm of Hannenhalli-Pevzner. The existence of short canonical
non-orientable systems of loops confirms a special case of a conjecture of
Negami on the joint crossing number of two embeddable graphs. We also provide a
correction for an argument of Negami bounding the joint crossing number of two
non-orientable graph embeddings.
