Even/odd dipaths in planar digraphs
Anna Galluccio, Martin Loebl · Optimization methods & software · 1994
In this paper we enlighten the structure of dipaths of prescribed parity in planar digraphs and we present a polynomial time algorithm for solving the following problem given a planar digraph G and a face F of G such that G – F has no even dicycle, find a dipath of prescribed parity between two specified vertices of F The same algorithm can be recursively applied to provide a polynomial time procedure for finding even dicycles in G (if any).