  Graphs are fundamental objects that find widespread applications across
computer science and beyond. Graph Theory has yielded deep insights about
structural properties of various families of graphs, which are leveraged in the
design and analysis of algorithms for graph optimization problems and other
computational optimization problems. These insights have also proved helpful in
understanding the limits of efficient computation by providing constructions of
hard problem instances. At the same time, algorithmic tools and techniques
provide a fresh perspective on graph theoretic problems, often leading to novel
discoveries. In this thesis, we exploit this symbiotic relationship between
graph theory and algorithms for graph optimization problems and beyond. This
thesis consists of three parts.
  In the first part, we study a graph routing problem called the Node-Disjoint
Paths (NDP) problem. Given a graph and a set of source-destination pairs of its
vertices, the goal is to route the maximum number of pairs via node-disjoint
paths. We come close to resolving the approximability of NDP by showing that it
is $n^{\Omega(1/poly\log\log n)}$-hard to approximate, even on grid graphs,
where n is the number of vertices. In the second part of this thesis, we use
graph decomposition techniques developed for efficient algorithms to derive a
graph theoretic result. We show that for every n-vertex expander graph G, if H
is any graph with at most $O(n/\log n)$ vertices and edges, then H is a minor
of G. In the last part, we show that the graph theoretic tools and graph
algorithmic techniques can shed light on problems seemingly unrelated to
graphs. We show that the randomized space complexity of the Longest Increasing
Subsequence (LIS) problem in the streaming model is intrinsically tied to the
query-complexity of the Non-Crossing Matching problem on graphs in a new model
of computation that we define.
