  The chosen tool of this thesis is an extremal type approach. The lesson drawn
by the theorems proved in the thesis is that surprisingly small compromise is
necessary on the efficacy of the solutions to make the approach work. The
problems studied have several connections to other subjects and practical
applications.
  The first part of the thesis is concerned with orthogonal art galleries. A
sharp extremal bound is proved on partitioning orthogonal polygons into at most
8-vertex polygons using established techniques in the field of art gallery
problems. This fills in the gap between already known results for partitioning
into at most 6- and 10-vertex orthogonal polygons.
  Next, these techniques are further developed to prove a new type of extremal
art gallery result. The novelty provided by this approach is that it
establishes a connection between mobile and stationary guards. This theorem has
strong computational consequences, in fact, it provides the basis for an
$\frac83$-approximation algorithm for guarding orthogonal polygons with
rectangular vision.
  In the second part, the graph theoretical concept of terminal-pairability is
studied in complete and complete grid graphs. Once again, the extremal approach
is conductive to discovering efficient methods to solve the problem.
  In the case of a complete base graph, the new demonstrated lower bound on the
maximum degree of realizable demand graphs is 4 times higher than previous best
results. The techniques developed are then used to solve the classical extremal
edge number problem for the terminal-pairability problem in complete base
graphs.
  The complete grid base graph lies on the other end of the spectrum in terms
density amongst path-pairable graphs. It is shown that complete grid graphs are
relatively efficient in routing edge-disjoint paths.
