MSc thesis of Spyridon Maniatis
Linkages in primal-dual graphs
Supervisor: Dimitrios M. Thilikos
One of the most influential bodies of work in Graph Theory has, undoubtedly, been the {\em Graph Minor series} of Neil Robertson and Paul D. Seymour, where, after $23$ papers during the years 1983-2011, they managed to prove {\em Wagner's conjecture}. This conjecture states that undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering, or, equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors. One can argue that it is not just the final result itself, but whole theory built during the procedure which had, and continues to have, a huge impact in both combinatorial and algorithmic Graph Theory. One of their main contributions, which also has a central role in their work, is constructing an algorithm that solves the {\sc Disjoint Paths} problem in $f(k) \cdot n^{3}$ steps, where $k$ is the number of disjoint paths that we are asked to find. The key ingredient of their proof is the so called {\em irrelevant-vertex technique} (for which full proofs only appeared in latter parts of the series), which has been used extensively thereafter. As great as this result was proved to be, the function $f$ of $k$ that appears in the running time is immense even for very small values of $k$. Therefore, many researchers tried to improve this parametric dependance on $k$, either by trying to simplify the complicated proofs of the structural theorems for the general case, or by restricting their attention to specific graph classes whose structural characteristics would hopefully lead to simpler proofs and better parametric dependance. A big step towards the first direction (although the bound of $f(k)$ is $2^{2^{2^{2^{\Omega(k)}}}}$ which is of course still huge) was made by Ken-ichi Kawarabayashi and Paul Wollan in \cite{Wollan}. A decisive step to the second direction, for the class of {\em planar graphs}, was made by Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos in \cite{PPDP}, where their bound for $f(k)$ is just single exponential on $k$. Based on this latter work, we study an extension of the {\sc Disjoint Paths} problem for the class of {\em pd-graphs} and, using on the idea of the irrelevant-vertex technique, we prove a structural theorem which states that if the treewidth of our pd-graph is sufficiently large, then there exists (and can be found algorithmically) a part of it which is irrelevant and whose removal leads to a simpler and equivalent instance. We also illustrate how an algorithm for the {\sc Disjoint Paths} problem for the class of pd-graphs can be used to construct algorithms for problems on plane graphs, where the it is essential to respect the topology of the plane embedding given as an input.
Defended: June 3, 2016.