Induced circuits in graphs on surfaces
Alexander Schrijver · Contemporary mathematics - American Mathematical Society · 1993
We show that for any fixed surface S there exists a polynomial-time algorithm to test if there exists an induced circuit traversing two given vertices r and s of an undirected graph G embedded on S. (An induced circuit is a circuit without chords.)The general problem (not fixing S) is NP-complete.In fact, for each fixed surface S there exists a polynomial-time to find a maximum number of r -s paths in G such that any two form an induced circuit.