  Finding a simple path of even length between two designated vertices in a
directed graph is a fundamental NP-complete problem known as the EvenPath
problem. Nedev proved in 1999, that for directed planar graphs, the problem can
be solved in polynomial time. More than two decades since then, we make the
first progress in extending the tractable classes of graphs for this problem.
We give a polynomial time algorithm to solve the EvenPath problem for classes
of H-minor-free directed graphs,1 where H is a single-crossing graph. We make
two new technical contributions along the way, that might be of independent
interest. The first, and perhaps our main, contribution is the construction of
small, planar, parity-mimicking networks. These are graphs that mimic parities
of all possible paths between a designated set of terminals of the original
graph. Finding vertex disjoint paths between given source-destination pairs of
vertices is another fundamental problem, known to be NP-complete in directed
graphs, though known to be tractable in planar directed graphs. We encounter a
natural variant of this problem, that of finding disjoint paths between given
pairs of vertices, but with constraints on parity of the total length of paths.
The other significant contribution of our paper is to give a polynomial time
algorithm for the 3-disjoint paths with total parity problem, in directed
planar graphs with some restrictions (and also in directed graphs of bounded
treewidth).
