Extremal solutions to some art gallery and terminal-pairability problems

Abstract

The thesis consists of two parts. In both parts, the problems studied are of significant interest, but are either NP-hard or unknown to be polynomially decidable. Realistically, this forces us to relax the objective of optimality or restrict the problem. As projected by the title, 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 (e.g., geometric algorithms, graph immersions, multi-commodity flow problem) and practical applications (e.g., VLSI design, image processing, routing traffic in networks)…