Edge-Disjoint Homotopic Paths in Straight-Line Planar Graphs
Alexander Schrijver · SIAM Journal on Discrete Mathematics · 1991
Let G be a planar graph, embedded without crossings in the euclidean plane $\mathbb{R}^2 $, and let $I_1 , \cdots ,I_p $ be some of its faces (including the unbounded face), considered as open sets. Suppose there exist (straight) line segments $L_1 , \cdots ,L_t $ in $\mathbb{R}^2 $ so that $G \cup I_1 \cup \cdots \cup I_p = L_1 \cup \cdots \cup L_t \cup I_1 \cup \cdots \cup I_p $ and so that each $L_i $ has its end points in $I_1 \cup \cdots \cup I_p $. Let $C_1 , \cdots ,C_k $ be curves in $\mathbb{R}^2 \backslash ( I_1 \cup \cdots \cup I_p )$ with end points in vertices of G. Conditions are described under which there exist pairwise edge-disjoint paths $P_1 , \cdots ,P_k $ in G so that $P_i $ is homotopic to $C_i $ in $\mathbb{R}^2 \backslash ( I_1 \cup \cdots \cup I_p ),$ for $i = 1, \cdots ,k$. This extends results of Kaufmann and Mehlhorn for graphs derived from the rectangular grid.