Induced circuits in planar graphs (Q1322013)

Previously the authors have given a polynomial-time algorithm for the problem of finding a minimum cost circuit without chords (induced circuit) traversing two given vertices of a planar graph. The algorithm is based on the Ellipsoid Method. Here we give an \(O(n^ 2)\) combinatorial algorithm to determine whether two nodes in a planar graph lie on an induced circuit. We also give a min-max relation for the problem of finding a maximum number of paths connecting two given vertices in a planar graph so that each pair of these paths forms an induced circuit.