Abstract
Let G = (V, E) be an undirected planar graph embedded in R2 with vertex set V and edge set E. Each edge e□E has a non-negative integral length l(e). Let (r1, s1) and (r2, s2) be two distinct pairs of vertices of G adjacent to the unbounded face. Let b1 and b2 be two positive integers. Given G, (r1, s1), (r2, s2), b1 and b2, we consider the problem of finding two vertex-disjoint paths P1 and P2 such that Pi is a path from ri to si and the length of Pi is at most bi for i = 1, 2. Previously, Holst and Pina [18] proposed a pseudo-polynomial time algorithm for this problem, which takes O(|V|^4*L^2) time, where L=max{b1, b2}. In this thesis, an improved algorithm is proposed. The proposed algorithm requires O(|V|^3*L^2) time.