Edge-Disjoint Homotopic Paths in Straight-Line Planar Graphs

摘要

Let G be a planar graph, embedded without crossings in the euclidean plane Rsq, and let I1, ..., Ip be some of its faces (including the unbounded face), considered as open sets. Suppose there exist (straight) line segments L1, ..., Lt in Rsq so that GuI1u...uIp = L1u...uLtuI1u...uIp and so that each Li has its end points in I1u...uIp. Let C1, ..., C1, be curves in Rsq/(I1u...uIp) with end points in vertices of G. Conditions under which there exist pairwise edge-disjoint paths P1, ..., Pk in G so that P1 is homotopic to Ci in Rsq/(I1u...uIp), for i = 1, ..., k are described. This extends results of Kaufmann and Mehlhorn (1986) for graphs derived from the rectangular grid.