Edge-Disjoint Homotopic Paths in a Planar Graph with One Hole

摘要

The following theorem, conjectured by Mehlhorn in relation to automated design of integrated circuits is proved. Let G = (V,E) be a planar graph, embedded in IRsq. Let O denote the anterior of some fixed bounded face. Let C1, ...,CK be curves in IRsq/(I union O), with end points in V intersection delta (I union O), so that for each Vertex v of G the degree of v in G has the same parity (mod 2) as the number of curves Ci beginning or ending in v (counting a curve beginning and ending in v for two). Then there exist pairwise edge-disjoint paths P1,..., PK in G so that Pi is homotopic to Ci in the space IRsq/(I union O) for i=1,...,k, if and only if for each dual path Q from I union O to I union O the number of edges in Q is not smaller than the number of times Q necessarily intersects the curves Ci. The theorem generalizes a theorem of Okamura and Seymour (1981). Its proof yields a polynomial-time algorithm finding the paths as required.