Disjoint homotopic paths and trees in a planar graph (Q1179127)

The author presents a polynomial-time algorithm for the following problem: Given a planar graph embedded in \(\mathbb{R}^ 2\), a subset \(\{I_ 1,\dots,I_ p\}\) of the faces of \(G\) (including the unbounded face), paths \(C_ 1,\dots,C_ k\) in \(G\) with endpoints on the boundary of \(I_ 1\cup\cdots\cup I_ p\), find pairwise disjoint simple paths \(P_ 1,\dots,P_ k\) in \(G\) so that, for each \(i=1,\dots,k\), \(P_ i\) is homotopic to \(C_ i\) in the space \(\mathbb{R}^ 2\backslash(I_ 1\cup\dots\cup I_ p)\). The algorithm is the basis for a theorem characterizing the existence of a solution to the above problem. Schrijver's neat procedure involves four steps: 1. Modifying the \(C_ i\) so they do not have self-crossings. 2. Obtaining a system \(Ax\leq b\) of linear inequalities representing how far the \(C_ i\) should be shifted to make them simple and pairwise disjoint. 3. Solving \(Ax\leq b\) in integers. 4. Shifting the \(C_ i\) according to the integer solution of \(Ax\leq b\). The author shows that his method can be extended to solve a problem of finding disjoint homotopic trees in a similar graph. In turn, this solution yields a polynomial-time algorithm for solving the following disjoint trees problem: If \(G\) is a planar graph embedded in \(\mathbb{R}^ 2\) and \(W_ 1,\dots,W_ k\) are pairwise disjoint vertex sets, find pairwise vertex-disjoint trees \(T_ 1,\dots,T_ k\) in \(G\) such that \(T_ i\) covers \(W_ i\).