Given vertices s, t of a planar digraph G, does there exist a directed circuit of G containing both s and t? We give a polynomial algorithm for this and for a number of related problems, including one about disjoint directed circuits of prescribed homotopy in a digraph drawn on a torus.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics
- AMS subject classification (1980): 05C70, 05C10, 05C20, 05C38