An Algorithmic Approach to Extremal Graph Problems (Thesis)
Report ID: TR-322-91Author: Han, Xiafeng
Date: 1991-06-00
Pages: 134
Download Formats: |PDF|
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.