An Algorithmic Approach to Extremal Graph Problems (Thesis)

Abstract:

The main purpose of this thesis is to study three problems concerning
extremal graphs. The first is the problem of finding a minimal 2-edge
connected subgraph of a 2-edge connected graph, the second is the
problem of finding a minimal 2-connected subgraph of a 2-connected
graph, and the third is the problem of finding a maximal planar
subgraph of a nonplanar graph. These problems are extensions of the
2-edge connectivity problem, the 2-connectivity problem, and the
planarity testing problem in graph theory. All three problems are
important in the theory of extremal graphs. They also have useful
applications in computer network and electronic circuit design.