Date of Award

2004

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Computer Science.

Supervisor

Tsin, Y. H.,

Rights

info:eu-repo/semantics/openAccess

Abstract

A graph is a mathematical abstraction that is useful in solving a variety of problems. NP-complete (Non-deterministic Polynomial) problems are computational problems for which there is no known polynomial time algorithm solving them. Unfortunately, many important graph theoretic problems are known to be NP-Complete for arbitrary graph. However, for some classes of graphs, polynomial time algorithms have been discovered. Owing to this reason, it is of both theoretical and practical interest to be able to tell if a given graph belongs to one of those classes. As a result, graph recognition has received considerable attention over the last few decades. It is well known that the Hamiltonian cycle problem is NP-Complete. However, for the class of outerplanar graphs, polynomial time algorithms for the Hamiltonian cycle problem have been proposed. In this thesis, we shall first study existing outerplanarity testing algorithms, and present a new outerplanarity testing algorithm which is optimal and much simpler than existing algorithms. The new algorithm proposed in this thesis is based on the depth-first search, an ear decomposition technique and a vertex/edge absorb operation. It is conceptually simple and is easy to implement. A rigorous proof for the correctness of the new algorithm is presented and its time complexity is analyzed.Dept. of Computer Science. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2004 .L56. Source: Masters Abstracts International, Volume: 43-05, page: 1753. Adviser: Y. H. Tsin. Thesis (M.Sc.)--University of Windsor (Canada), 2004.

Download

Share

COinS