A Structural Theorem for Shortest Vertex-Disjoint Paths Computation in Planar Graphs
Given k terminal pairs (s_1,t_1),(s_2,t_2), ..., (s_k,t_k) in an edge-weighted graph G, the k Shortest Vertex-Disjoint Paths problem is to find a collection P_1, P_2, ..., P_k of vertex-disjoint
paths with minimum total length, where P_i is an s_i-to-t_i path. As a special case of the multi-commodity flow problem, computing vertex disjoint paths has found several applications, for example
in VLSI design, or network routing.

In this thesis we describe a Structural Theorem for a special case of the Shortest Vertex-Disjoint Paths problem in undirected planar graphs where the terminal vertices are on the boundary of the
outer face. At a high level, our Structural Theorem bounds the number of crossings between the i'th path of k Shortest Vertex-Disjoint Paths with the i'th path of k-1 Shortest Vertex-Disjoint Paths
problem and guarantees that the i'th path of the k Shortest Vertex-Disjoint paths does not cross j'th (j != i) path of the k-1 Vertex-Disjoint Paths problem.

This Structural Theorem can be used to obtain an n^O(k^3) algorithm for the k Shortest Vertex-Disjoint Paths problem.

Co-Major Advisor: Amir Nayyeri
Co-Major Advisor: Glencora Borradaile
Committee: Eugene Zhang
GCR: Abi Farsoni