Disjoint homotopic paths and trees in a planar graph |
| |
Authors: | A Schrijver |
| |
Institution: | (1) Mathematical Centre, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands;(2) University of Amsterdam, Amsterdam, The Netherlands |
| |
Abstract: | In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ2, a subset {I
1, …,I
p} of the faces ofG, and pathsC
1, …,C
k inG, with endpoints on the boundary ofI
1 ∪ … ∪I
p; find: pairwise disjoint simple pathsP
1, …,P
k inG so that, for eachi=1, …,k, P
i is homotopic toC
i in the space ℝ2\(I
1 ∪ … ∪I
p).
Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm
to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ2 and pairwise disjoint setsW
1, …,W
k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT
1, …,T
k ofG whereT
i
(i=1, …, k). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|